#include <stdio.h>

#define N 1000

void main()
{
	/*int i, p, q, t, id[N];

	for(i = 0; i < N; i++) id[i] = i;
	while(scanf("%d %d", &p, &q) == 2)
	{
		if (id[p] == id[q]) continue;

		for (t = id[p], i = 0; i < N; i++)
		{
			if (id[i] == t) id[i] = id[q];

			printf("%d %d\n", p, q);
		}
	}*/

	int i, j, k;
	long int count = 0;

	for (i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)
		
			for (k = 0; k < N; k++)
		

		count++;
			printf("%d\n",count);
	}
}


BMP

BMP是一种与硬件设备无关的图像文件格式，使用非常广。它采用位映射存储格式，除了图像深度可选以外，不采用其他任
何压缩，因此，BMP文件所占用的空间很大。BMP文件的图像深度可选lbit、4bit、8bit及24bit。BMP文件存储数据时，图
像的扫描方式是按从左到右、从下到上的顺序。 

由于BMP文件格式是Windows环境中交换与图有关的数据的一种标准，因此在Windows环境中运行的图形图像软件都支持BMP图像
格式。 

典型的BMP图像文件由三部分组成：位图文件头数据结构，它包含BMP图像文件的类型、显示内容等信息；位图信息数据结构，
它包含有BMP图像的宽、高、压缩方法，以及定义颜色等信息。

具体数据举例：
如某BMP文件开头：
424D 4690 0000 0000 0000 4600 0000 2800 0000 8000 0000 9000 0000 
0100*1000 0300 0000 0090 0000 A00F 0000 A00F 0000 0000 0000 0000 
0000*00F8 0000 E007 0000 1F00 0000 0000 0000*02F1 84F1 04F1 84F1 
84F1 06F2 84F1 06F2 04F2 86F2 06F2 86F2 86F2 .... ....

BMP文件可分为四个部分：位图文件头、位图信息头、彩色板、图像数据阵列，在上图中已用*分隔。 

一、图像文件头 
　　1）1：(这里的数字代表的是"字",即两个字节,下同)图像文件头。424Dh=’BM’，表示是Windows支持的BMP格式。 
　　2）2-3：整个文件大小。4690 0000，为00009046h=36934。 
　　3）4-5：保留，必须设置为0。 
　　4）6-7：从文件开始到位图数据之间的偏移量。4600 0000，为00000046h=70，上面的文件头就是35字=70字节。 
　　5）8-9：位图图信息头长度。 
　　6）10-11：位图宽度，以像素为单位。8000 0000，为00000080h=128。 
　　7）12-13：位图高度，以像素为单位。9000 0000，为00000090h=144。 
　　8）14：位图的位面数，该值总是1。0100，为0001h=1。

二、位图信息头 
　　9）15：每个像素的位数。有1（单色），4（16色），8（256色），16（64K色，高彩色），24（16M色，真彩色），
32（4096M色，增强型真彩色）。1000为0010h=16。 
　　10）16-17：压缩说明：有0（不压缩），1（RLE 8，8位RLE压缩），2（RLE 4，4位RLE压缩，3（Bitfields，位域存放）。
RLE简单地说是采用像素数+像素值的方式进行压缩。T408采用的是位域存放方式，用两个字节表示一个像素，位域分配为r5b6g5。
图中0300 0000为00000003h=3。 
　　11）18-19：用字节数表示的位图数据的大小，该数必须是4的倍数，数值上等于位图宽度×位图高度×每个像素位数。
		0090 0000为00009000h=80×90×2h=36864。 
　　12）20-21：用象素/米表示的水平分辨率。A00F 0000为0000 0FA0h=4000。 
　　13）22-23：用象素/米表示的垂直分辨率。A00F 0000为0000 0FA0h=4000。 
　　14）24-25：位图使用的颜色索引数。设为0的话，则说明使用所有调色板项。 
　　15）26-27：对图象显示有重要影响的颜色索引的数目。如果是0，表示都重要。 

三、彩色板 
　　16）28-35：彩色板规范。对于调色板中的每个表项，用下述方法来描述RGB的值： 
　　1字节用于蓝色分量 
　　1字节用于绿色分量 
　　1字节用于红色分量 
　　1字节用于填充符(设置为0) 
　　对于24-位真彩色图像就不使用彩色板，因为位图中的RGB值就代表了每个象素的颜色。 
　　如，彩色板为00F8 0000 E007 0000 1F00 0000 0000 0000，其中： 
　　00FB 0000为FB00h=1111100000000000（二进制），是红色分量的掩码。 
　　E007 0000为 07E0h=0000011111100000（二进制），是绿色分量的掩码。 
　　1F00 0000为001Fh=0000000000011111（二进制），是红色分量的掩码。 
　　0000 0000总设置为0。 
　　将掩码跟像素值进行“与”运算再进行移位操作就可以得到各色分量值。看看掩码，就可以明白事实上在每个像素值
的两个字节16位中，按从高到低取5、6、5位分别就是r、g、b分量值。取出分量值后把r、g、b值分别乘以8、4、8就可以
补齐第个分量为一个字节，再把这三个字节按rgb组合，放入存储器（同样要反序），就可以转换为24位标准BMP格式了。

四、图像数据阵列 
　　17)17-．．．：每两个字节表示一个像素。阵列中的第一个字节表示位图左下角的象素，而最后一个字节表示位图右
   上角的象素。  


SPFA

求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm。 
从名字我们就可以看出，这种算法在效率上一定有过人之处。 
很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，
SPFA算法便派上用场了。 
简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，
以判断是否存在负权回路，但这不是我们讨论的重点。 
我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出
的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行
松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来
进行松弛操作，直至队列空为止。 

定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。 
证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法
的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，
随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕） 

SPFA(G,w,s) 
1. INITIALIZE-SINGLE-SOURCE(G,s) 
2. INITIALIZE-QUEUE(Q) 
3. ENQUEUE(Q,s) 
4. While Not EMPTY(Q)  
5.   Do u<-DLQUEUE(Q) 
6.   For 每条边(u,v) in E[G] 
7.   Do tmp<-d[v] 
8.   Relax(u,v,w) 
9.   If (d[v] < tmp) and (v不在Q中) 
10.   ENQUEUE(Q,v) 


期望的时间复杂度O(e)  


对称算法
 对称密码算法有时又叫传统密码算法，就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，
 加密解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定一个密钥。
 对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加密解密。只要通信需要保密，密钥就必须保密。
 对称算法的加密和解密表示为：

Ek(M)=C

Dk(C)=M

对称算法可分为两类。一次只对明文中的单个位（有时对字节）运算的算法称为序列算法或序列密码。另一类算法是对明文的
一组位进行运算，这些位组称为分组，相应的算法称为分组算法或分组密码。现代计算机密码算法的典型分组长度为
64位――这个长度大到足以防止分析破译，但又小到足以方便作用。

这种算法具有如下的特性：

Dk(Ek(M))=M

常用的采用对称密码术的加密方案有5个组成部分（如图所示）

l）明文：原始信息。

2)加密算法：以密钥为参数，对明文进行多种置换和转换的规则和步骤，变换结果为密文。

3)密钥：加密与解密算法的参数，直接影响对明文进行变换的结果。

4)密文：对明文进行变换的结果。

5)解密算法：加密算法的逆变换，以密文为输入、密钥为参数，变换结果为明文。

对称密码术的优点在于效率高（加／解密速度能达到数十兆／秒或更多），算法简单，系统开销小，适合加密大量数据。

尽管对称密码术有一些很好的特性，但它也存在着明显的缺陷，包括：

l）进行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况下是可行的，但在某些情况下会非常困难，甚至无法实现。

2)规模复杂。举例来说，A与B两人之间的密钥必须不同于A和C两人之间的密钥，否则给B的消息的安全性就会受到威胁。
在有1000个用户的团体中，A需要保持至少999个密钥（更确切的说是1000个，如果她需要留一个密钥给他自己加密数据）。
对于该团体中的其它用户，此种倩况同样存在。这样，这个团体一共需要将近50万个不同的密钥！推而广之，n个用户的团体
需要N2/2个不同的密钥。

通过应用基于对称密码的中心服务结构，上述问题有所缓解。在这个体系中，团体中的任何一个用户与中心服务器
（通常称作密钥分配中心）共享一个密钥。因而，需要存储的密钥数量基本上和团体的人数差不多，而且中心服务器也
可以为以前互相不认识的用户充当“介绍人”。但是，这个与安全密切相关的中心服务器必须随时都是在线的，因为只要
服务器一掉线，用户间的通信将不可能进行。这就意味着中心服务器是整个通信成败的关键和受攻击的焦点，也意味着它
还是一个庞大组织通信服务的“瓶颈”  


龙格库塔
龙格-库塔(Runge-Kutta)方法是一种在工程上应用广泛的高精度单步算法。由于此算法精度高，采取措施对误差进行抑制，
所以其实现原理也较复杂。该算法是构建在数学支持的基础之上的。对于一阶精度的欧拉公式有： 

　　yi＋１＝yi＋h*K1 
　　K1=f(xi,yi) 

　　当用点xi处的斜率近似值K1与右端点xi＋１处的斜率K2的算术平均值作为平均斜率K*的近似值，那么就会得到二阶精度
的改进欧拉公式： 

　　yi＋１＝yi＋h*( K1+ K2)/2 
　　K1=f(xi,yi) 
　　K2=f(xi+h,yi+h*K1) 

　　依次类推，如果在区间[xi,xi+1]内多预估几个点上的斜率值K1、K2、……Km，并用他们的加权平均数作为平均斜率K*的近
似值，显然能构造出具有很高精度的高阶计算公式。经数学推导、求解，可以得出四阶龙格－库塔公式，也就是在工程中应用广
泛的经典龙格－库塔算法： 

　　yi＋１＝yi＋h*( K1+ 2*K2 +2*K3+ K4)/6 
　　K1=f(xi,yi) 
　　K2=f(xi+h/2,yi+h*K1/2) 
　　K3=f(xi+h/2,yi+h*K2/2) 
　　K4=f(xi+h,yi+h*K3)  


逆序对

设A[1..n]是一个包含N个非负整数的数组。如果在i〈 j的情况下，有A〉a[j]，则(i,j)就称为A中的一个逆序对。

例如，数组（3，1，4，5，2）的“逆序对”有<3,1>,<3,2><4,2><5,2>，共4个。 


遗传算法
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；
具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索
方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工
生命等领域。它是现代有关智能计算中的关键技术。

遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，
是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编
码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函
数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法
以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐
渐成为重要的智能算法之一。

遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：

创建一个随机的初始状态

初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的
情况不一样，在那里问题的初始状态已经给定了。

评估适应度

对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要
把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。

繁殖(包括子代突变)

带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结
合而成，这个过程被称为“杂交”。

下一代

如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，
新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。

并行计算

非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体
根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”
节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。


---------来个例子，大家好理解------------
                               基于遗传算法的人工生命模拟 
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
#include<time.h>
#include<string.h>
#include "graph.c"
/* 宏定义 */
#define TL1      20          /* 植物性食物限制时间 */
#define TL2      5           /* 动物性食物限制时间 */
#define NEWFOODS 3           /* 植物性食物每代生成数目  */
#define MUTATION 0.05        /* 变异概率     */
#define G_LENGTH  32         /* 个体染色体长度  */
#define MAX_POP  100         /* 个体总数的最大值  */
#define MAX_FOOD 100         /* 食物总数的最大值  */
#define MAX_WX    60         /* 虚拟环境的长度最大值 */
#define MAX_WY    32         /* 虚拟环境的宽度最大值 */
#define SX1      330         /* 虚拟环境图左上角点x坐标  */
#define SY1      40          /* 虚拟环境图左上角点y坐标  */
#define GX       360         /* 个体数进化图形窗口的左上角点X坐标  */
#define GY       257         /* 个体数进化图形窗口的左上角点Y坐标  */
#define GXR      250         /* 个体数进化图形窗口的长度    */
#define GYR      100         /* 个体数进化图形窗口的宽度    */
#define GSTEP     2          /* 个体数进化图形窗口的X方向步长    */
#define R_LIFE  0.05         /* 初期产生生物数的环境比率 */
#define R_FOOD  0.02         /* 初期产生食物数的环境比率 */
#define SL_MIN    10         /* 个体寿命最小值   */
/* 全局变量 */
unsigned  char  gene[MAX_POP][G_LENGTH];     /* 遗传基因      */
unsigned  char  iflg[MAX_POP];               /* 个体死活状态标志变量  */
unsigned  char  fflg[MAX_FOOD];              /* 食物有无状态标志变量  */
unsigned  char  world[MAX_WX][MAX_WY];       /* 虚拟环境的数据    */
unsigned char                                /* 各中行为模式数据 */
life1[5][5]={{0,0,1,0,0},{0,1,0,1,0},{1,0,0,0,1},{0,1,0,1,0},{0,0,1,0,0}};
unsigned char
life2[5][5]={{1,1,1,1,1},{1,0,0,0,1},{1,0,0,0,1},{1,0,0,0,1},{1,1,1,1,1}};
unsigned char
food1[5][5]={{0,0,0,1,0},{0,0,1,1,0},{0,1,0,1,0},{0,0,1,1,0},{0,0,0,1,0}};
unsigned char
food2[5][5]={{0,0,0,1,0},{0,0,1,1,0},{0,1,1,1,0},{0,0,1,1,0},{0,0,0,1,0}};
int pop_size;                   /* 个体总数   */
int iatr[MAX_POP][4];           /* 个体属性   */
                                /* iatr[][0]  个体当前位置x坐标  */
                                /* iatr[][1]  个体当前位置y坐标  */
                                /* iatr[][2]  内部能量  */
                                /* iatr[][3]  年龄属性  */
int food_size;                  /* 食物总数  */
int fatr[MAX_FOOD][4];          /* 食物属性  */
                                /* fatr[][0]  食物当前位置x坐标  */
                                /* fatr[][1]  食物当前位置y坐标  */
                                /* fatr[][2]=0 : 植物性 =1:动物性 */
                                /* fatr[][3]  新鲜程度    */
int wx,wy;                      /* 虚拟环境的长宽度  */

void uni_crossover(gene,g1,g2,g3,ratio1,g_length)    /* 均匀交叉 */
unsigned char *gene;                                 /* 遗传基因 */
int g1,g2,g3;                                        /* g1 g2 父个体编号  g3 子个体编号  */
double ratio1;                                       /*  父个体g1被选中的概率  */
int g_length;                                        /* 个体遗传基因的位长  */
{
   unsigned char *gene1;        /*  父1遗传基因的指针 */
   unsigned char *gene2;        /*  父2遗传基因的指针 */
   unsigned char *gene3;        /*  子遗传基因的指针 */
   double rnd,r1;
   int i;
   gene1=gene+g_length*g1;
   gene2=gene+g_length*g2;
   gene3=gene+g_length*g3;
   r1=(int)(10000.0*ratio1);
   for(i=0;i<g_length;i++)
   {  rnd=random(10000);
      if(rnd<=r1)    *(gene3+i)=*(gene1+i);
      else           *(gene3+i)=*(gene2+i);
   }
}

void g_disp_unit(x,y,n) 
/* 绘制虚拟环境的一个单元  */
int x,y;        /* x=0,1,2....,wx-1;   y=0,1,2,....,wy-1  */
int n;          /* n=0: =1: 生物1  =2:生物2   =3:植物性食物  =4:障碍物  =5:动物性食物 */
{
   int gx,gy,i,j;
   unsigned char col;
   gx=SX1+5*x;gy=SY1+5*y;
   for(i=0;i<5;i++)
     for(j=0;j<5;j++)
     {  switch(n)
          { case 0: col=0;             break;
            case 1: col=life1[j]*2; break;
            case 2: col=life2[j]*4; break;
            case 3: col=food1[j]*6; break;
            case 4: col=7;             break;
            case 5: col=food2[j]*11;
           }
         g_pset(gx+j,gy+i,col);
       }
   }

void g_draw_world()         /* 显示虚拟环境画面  */
{
int i,j;
for(i=0;i<wy;i++)
  for(j=0;j<wx;j++)
  g_disp_unit(j,i,world[j]);
}

void g_draw_frame(x1,y1,x2,y2,c1,c2,c3,c4,text)
int x1,y1,x2,y2,c1,c2,c3,c4;
char *text;
{  int n,x3;
   g_rectangle(x1,y1,x2,y2,c1,1);
   g_rectangle(x1,y1,x2,y2,c2,0);
   g_rectangle(x1,y1,x2,y1+16,c3,1);
   g_rectangle(x1,y1,x2,y1+16,c2,0);
   n=strlen(text);
   x3=x1+((x2-x1-n*8)/2);
   disp_hz16(text,x3,y1,c4);
}

void g_init_frames()      /*  初始化画面  */
{
  int i,j,cx,cy,x,y;
  char text[17];
  g_draw_frame(0,0,639,399,15,0,4,15,
      "基于遗传算法的人工生命模拟");
  g_draw_frame(0,16,320,170,7,0,8,15,"设定参数");
  y=48;
   setcolor(9);
  disp_hz16("植物食物限制时间",16,y,15);
  sprintf(text,"%d",TL1);
  g_text(200,y+8,4,text);
  y=y+24;
   setcolor(9);
  disp_hz16("动物食物限制时间",16,y,15);
  sprintf(text,"%d",TL2);
  g_text(200,y+8,4,text);
  y=y+24;
   setcolor(9);
  disp_hz16("植物食物每代生成个数",16,y,15);
  sprintf(text,"%d",NEWFOODS);
  g_text(200,y+8,4,text);
  y=y+24;
   setcolor(9);
  disp_hz16("变异概率",16,y,15);
  i=(int)(MUTATION*100.0);
  sprintf(text,"%d",i);
  g_text(152,y+8,4,text);
  g_draw_frame(0,170,320,399,7,0,8,15,"最佳基因型");
  x=16;y=194;
   setcolor(9);
  disp_hz16("SP:物种号........",x,y,15);y=y+16;
  disp_hz16("SL:寿命..........",x,y,15);y=y+16;
  disp_hz16("VF:视野..........",x,y,15);y=y+16;
  disp_hz16("TM:基本移动模式..",x,y,15);y=y+16;
  disp_hz16("CM:移动特点......",x,y,15);y=y+16;
  disp_hz16("LM:移动能耗......",x,y,15);y=y+16;
  disp_hz16("CA:行动特点......",x,y,15);y=y+16;
  disp_hz16("CR:善变性........",x,y,15);y=y+16;
  disp_hz16("SA:攻击速度......",x,y,15);y=y+16;
  disp_hz16("DA:防御能力......",x,y,15);y=y+16;
  disp_hz16("LA:攻击能耗......",x,y,15);y=y+16;
  disp_hz16("EF:食物吸取效率..",x,y,15);y=y+16;
  g_draw_frame(320,16,639,207,7,0,8,15,"虚拟世界");
  g_draw_frame(320,207,639,399,7,0,8,15,"世代个体数目变化");
  }

void g_init_graph() 
/*  个体数进化图初始化  */
{
   g_rectangle(GX,GY,GX+GXR,GY+GYR,0,1);
   g_rectangle(GX,GY,GX+GXR,GY+GYR,6,0);
   setcolor(1);
   disp_hz16( "生物 1",GX+5,GY-18,15);
   g_line(GX+90,GY-10,GX+110,GY-10,1);
   setcolor(4);
   disp_hz16( "生物 2",GX+120,GY-18,15);
   g_line(GX+205,GY-10,GX+225,GY-10,4);
   setcolor(0);
   disp_hz16("世代数",GX+168,GY+GYR+10,15);
   g_text(GX-25,GY,0,"100");
   g_text(GX-14,GY+GYR,0,"0");
}

void g_plot_population(gen_num,n1,n2,n1old,n2old)
int gen_num,n1,n2,n1old,n2old;
{
  int x,y,gx,gy,x_old,y_old;
  char text[8];
  if(gen_num%10==0)
  {
     x=GX+(gen_num-1)*GSTEP;
     g_line(x,GY+1,x,GY+GYR-1,1);
     sprintf(text,"%d",gen_num);
     if(gen_num<100||gen_num%20==0)
      g_text(x-8,GY+GYR+5,15,text);
  }
  x_old=GX+(gen_num-1)*GSTEP;
  x=x_old+GSTEP;
  y_old=GY+GYR-n1old;
  y=GY+GYR-n1;
  g_line(x_old,y_old,x,y,1);
  y_old=GY+GYR-n2old;
  y=GY+GYR-n2;
  g_line(x_old,y_old,x,y,4);
}

void g_disp_genotype()             /* 显示最佳个体的遗传基因型  */
{
  int i,j,n0,n1,x,y;
  unsigned char g[G_LENGTH];
  unsigned char bits[12][2]=
  { {0,0},{1,4},{5,6},{7,8},{9,11},{12,12},{13,15},
    {16,18},{19,21},{22,24},{25,27},{28,31}};
   /*  画面消除  */
   g_rectangle(200,187,319,398,7,1);
    if(pop_size!=0)
    {
     /* 获取各遗传因子 */
      for(i=0;i<G_LENGTH;i++)
      {
        n0=0;n1=0;
        for(j=0;j<pop_size;j++)
         if(gene[j]==0) n0++;
         else  n1++;
         if(n0>=n1) g=0; else g=1;
      }
      x=220;
      for(i=0;i<12;i++)
      {
        y=202+i*16;
        for(j=bits[0];j<=bits[1];j++)
        if(g[j]==0)
          g_text(x+(j-bits[0])*16,y,4,"0");
          else
          g_text(x+(j-bits[0])*16,y,4,"1");
          }
      }
  }

void g_disp_char(x,y,x1,y1,x2,y2,v) 
int x,y,x1,y1,x2,y2;
unsigned char v;
{
   char c[10];
   if(x>=x1&& x<=x2-8 && y>=y1 && y<=y2-10)
   {
   switch(v)
    {
        case 0: strcpy(c,"0\0");break;
        case 1: strcpy(c,"+\0");break;
        case 2: strcpy(c,"-\0");break;
        case 3: strcpy(c,"x\0");
   }
   g_text(x,y,15,c);
   }
}
void remove_life(n)               /* 消除第n个个体  */
int n;
{
  iflg[n]=0;
  world[iatr[n][0]][iatr[n][1]]=0;
  g_disp_unit(iatr[n][0],iatr[n][1],0);
  if(food_size+1<=MAX_FOOD)
  {
  food_size++;
  fatr[food_size-1][0]=iatr[n][0];
  fatr[food_size-1][1]=iatr[n][1];
  fatr[food_size-1][2]=1;
  fatr[food_size-1][3]=0;
  fflg[food_size-1]=1;
  world[iatr[n][0]][iatr[n][1]]=5;
  g_disp_unit(iatr[n][0],iatr[n][1],5);
  }
}

void  remove_food(n)              /* 消除第n个食物 */
int n;
{
  fflg[n]=0;
  world[fatr[n][0]][fatr[n][1]]=0;
  g_disp_unit(fatr[n][0],fatr[n][1],0);
  }

void make_lives_and_foods()         /* 设置虚拟环境中生物与食物  */
{
  int x,y,i,j;
  pop_size=0;
  food_size=0;
  for(y=0;y<wy;y++)
    for(x=0;x<wx;x++)
    {
      if(world[x][y]==1||world[x][y]==2)
      {
       if(pop_size+1<=MAX_POP)
       {
         pop_size++;
        /* 生成遗传因子 */
           gene[pop_size-1][0]=world[x][y]-1;
           for(i=1;i<G_LENGTH;i++)
             gene[pop_size-1]=random(2);
           /*  设定属性  */
            iatr[pop_size-1][0]=x;
            iatr[pop_size-1][1]=y;
            iatr[pop_size-1][2]=70+random(30);
            iatr[pop_size-1][3]=random(SL_MIN);
            }
       }
       if(world[x][y]==3||world[x][y]==5)
       {
         if(food_size+1<=MAX_FOOD)
         {
         food_size++;
         /* 设定属性  */
         fatr[food_size-1][0]=x;
         fatr[food_size-1][1]=y;
         if(world[x][y]==3)
              fatr[food_size-1][2]=0;
         else
              fatr[food_size-1][2]=1;
        fatr[food_size-1][3]=random(TL1-1)+1;
        }
      }
    }
}

void find_empty(x,y)              /* 寻找虚拟环境中的空处，返回坐标  */
  int *x,*y;
  {
  int ok;
  ok=0;
  while(ok==0)
  {
   *x=random(wx);*y=random(wy);
   if(world[*x][*y]==0) ok=1;
   }
  }

void make_world()                 /* 随机设定人工环境  */
{
int i,j,k,num,x,y;
int ok,overlap;
char choice[3];
double size;
wx=0;
while(wx<10||wx>MAX_WX)
{
     setcolor(15);
     disp_hz16("虚拟环境长度(10-60)",10,210,20);
     gscanf(300,210,4,0,3,"%s",choice);
     wx=atoi(choice);
  }
wy=0;
while(wy<10||wy>MAX_WY)
{
     setcolor(15);
     disp_hz16("虚拟环境宽度(10-32)",10,240,20);
     gscanf(300,240,4,0,3,"%s",choice);
     wy=atoi(choice);
  }
for(i=0;i<wy;i++)
  for(j=0;j<wx;j++)
   if(i==0||i==wy-1||j==0||j==wx-1)
    world[j]=4;
    else    world[j]=0;
/* 设定障碍物  */
size=(double)(wx*wy);
num=(int)(size/40.0);
if(num>MAX_POP)  num=MAX_POP;
for(i=0;i<num;i++)
{
   find_empty(&x,&y);
   world[x][y]=4;
   }
num=(int)(size/5.0);
if(num>MAX_FOOD) num=MAX_FOOD;
for(i=0;i<num;i++)
{
ok=0;
while(ok==0)
{
    x=random(wx);y=random(wy);
    if((world[x][y]!=4) &&
       (world[x][y-1]==4 || world[x][y+1]==4 ||
        world[x-1][y]==4 || world[x+1][y]==4))
        {  world[x][y]=4;
           ok=1;
           }
    }
}

  for(y=0;y<wy;y++)
  for(x=0;x<wx;x++)
    if(world[x][y]==0)
    {
    num=0;
    for(i=-1;i<=1;i++)
     for(j=-1;j<=1;j++)
       if(get_world(x+j,y+i)==4)
       num++;
       if(num>=6) world[x][y]=4;
       }
  /*  设定生物  */
  num=(int)(size*R_LIFE);
  for(i=0;i<num;i++)
  {  find_empty(&x,&y);
     world[x][y]=random(2)+1;
     }
  /* 设定食物  */
  num=(int)(size*R_FOOD);
  for(i=0;i<num;i++)
     {
     find_empty(&x,&y);
     world[x][y]=3;
}
}

void load_world_file()         /* 读取虚拟环境数据文件设定  */
{
FILE *fopen(),*fpt;
char st[100],c;
int i,j;
if((fpt=fopen("\\ga\\world","r"))==NULL) exit(-1);
else
{
   fscanf(fpt,"%d",&wx);
   fscanf(fpt,"%d",&wy);
   for(i=0;i<wy;i++)
    for(j=0;j<wx;j++)
    fscanf(fpt,"%d",&world[j]);
    fclose(fpt);
    }
}

int get_world(x,y)             /*坐标(x,y)处环境值  */
int x,y;
{
   if(x>=0 && x<wx && y>=0 && y<wy)
   return(world[x][y]);
  else
  return(-1);
}

int  decode_gene(n,sb,bw)               /* 第n个个体基因型解码  */
int  n,sb,bw;                           /*  sb开始位  bw位长 */
{
  int i,sum;
  sum=0;
  for(i=sb;i<sb+bw;i++)
  sum=sum*2+gene[n];
  return(sum);
  }

void  move_pos(n,x1,y1,x2,y2)          /* 个体n从(x1,y1)移动到(x2,y2)   */
int n,x1,y1,x2,y2;
{
  int sp,loss;
  loss=decode_gene(n,12,1)+1;          /* 移动消耗 */
  iatr[n][2]=iatr[n][2]-loss;          /*  内部能量更新 */
  if(iatr[n][2]<=0)  remove_life(n);
  else
  {
    /* 个体属性更新 */
    iatr[n][0]=x2;iatr[n][1]=y2;       /* x,y坐标更新 */
    /* 显示更新 */
    sp=gene[n][0]+1;
    g_disp_unit(x1,y1,0);              /*  当前位置(x,y)图形消除 */
    world[x1][y1]=0;
    g_disp_unit(x2,y2,sp);             /*  新位置图形表示 */
    world[x2][y2]=sp;
  }
}

void  move_randomly(n)                /*  个体n按照移动模式随机移动 */
int n;
{
  
/* 基本移动模式1  */
int  pat1[8][2]={{1,0},{1,1},{0,1},{-1,1},
                  {-1,0},{-1,-1},{0,-1},{1,-1}};
  /* 基本移动模式2与3  */
int pat2_3[2][4][2]={{{1,0},{0,1},{-1,0},{0,-1}},
                  {{1,1},{-1,1},{-1,-1},{1,-1}}};
int pat,x1,y1,x2,y2,rndnum;
pat=decode_gene(n,7,2);
                              /* pat(0,1,2,3): 表示基本移动模式  */
x1=iatr[n][0];               /* 当前x坐标 */
y1=iatr[n][1];               /* 当前y坐标 */
if(pat<=1)                   /* 基本移动模式1  */
{
   rndnum=random(8);
   x2=x1+pat1[rndnum][0];     /* 移动目的点x坐标 */
   y2=y1+pat1[rndnum][1];     /* 移动目的点y坐标 */
   }
else                         /* 基本移动模式2与3  */
{
   rndnum=random(4);
   x2=x1+pat2_3[pat-2][rndnum][0];
   y2=y1+pat2_3[pat-2][rndnum][1];
   }
   if(x2>=0 && x2<wx && y2>=0 && y2<wy)
    if(get_world(x2,y2)==0)
      move_pos(n,x1,y1,x2,y2);
   /* 非法目的点的场合不作移动 */
}

void  move_individual(n)      /* 个体n移动 */
int n;
{
int cx,cy,dx,dy,sp,vf,sumx,sumy;
int i,j,a,sgn[3],num;
double  vect[8][2]={{1,0},{1,1},{0,1},{-1,1},
                  {-1,0},{-1,-1},{0,-1},{1,-1}};
double vx,vy,d1,d2;
double _cos,cos_max;
cx=iatr[n][0];                /* 当前x坐标 */
cy=iatr[n][1];                /* 当前y坐标 */
sp=decode_gene(n,0,1)+1;      /* 生物种1和2 */
for(i=0;i<3;i++)              /* 移动特点CM */
{
sgn=decode_gene(n,9+i,1);
if(sgn==0)  sgn=-1;
}
sumx=0;sumy=0;num=0;
vf=decode_gene(n,5,2)+1;        /* 视野  */
  for(i=-vf;i<=vf;i++)
   for(j=-vf;j<=vf;j++)
   {
   if(i!=0||j!=0)
   {
     a=get_world(cx+j,cy+i);
     if(a==1||a==2)            /* 生物 1和2  */
     {   num++;
     if(a==sp)                 /* 同种生物 */
     {
     sumx=sumx+sgn[0]*j;
     sumy=sumy+sgn[0]*i;
     }
     else                      /* 异种生物 */
     {
     sumx=sumx+sgn[1]*j;
     sumy=sumy+sgn[1]*i;
     }
  } else
  if(a==3||a==5)               /*  食物  */
    {
    num++;
    sumx=sumx+sgn[2]*j;
    sumy=sumy+sgn[2]*i;
    }
   }
  }
if(num!=0)                     /* 视野内有其他生物和食物时 */
{
vx=(double)sumx/(double)num;
vy=(double)sumy/(double)num;
if(vx!=0||vy!=0)
{
      cos_max=-1.0;
      j=0;
      for(i=0;i<8;i++)
      {
        d1=sqrt(vx*vx+vy*vy);
        d2=sqrt(vect[0]*vect[0]+vect[1]*vect[1]);
        _cos=(vx*vect[0]+vy*vect[1])/d1/d2;
        if(_cos>cos_max)
        {
         cos_max=_cos;j=i;
         }
      }
  dx=cx+(int)vect[j][0];
  dy=cy+(int)vect[j][1];
  if(dx>=0 && dx<wx && dy>=0 && dy<wy)
    if(world[dx][dy]==0)
      move_pos(n,cx,cy,dx,dy);
  }
  else  move_randomly(n);
}
else  move_randomly(n);
/* 视野内有其他生物和食物时 */
}

void  act1_attack(n)                /*  个体 n攻击行动范围内的其他生物个体 */
int n;
{
  int sft[8][2]={{1,0},{1,1},{0,1},{-1,1},
                  {-1,0},{-1,-1},{0,-1},{1,-1}};
  int x1,y1,x2,y2,n2;
  int found,rndnum;
  double attack1,attack2,sa1,sa2,da1,da2,rnd1,rnd2,La1,La2;
  x1=iatr[n][0];y1=iatr[n][1];
  /* 获得攻击对象的坐标(x2,y2) */
  found=0;
  while(found==0)
  {
   rndnum=random(8);
   x2=x1+sft[rndnum][0];
   y2=y1+sft[rndnum][1];
   if(get_world(x2,y2)==1||get_world(x2,y2)==2)
   found=1;
   }
   /* 检查攻击对象个体号n2  */
   found=0;n2=0;
   while(found==0)
   {
     if(iatr[n2][0]==x2 && iatr[n2][1]==y2 && iflg[n2]==1)
     found=1;  else n2++;
   }
   /* 计算双方的 Attack量 */
   sa1=(double)decode_gene(n,19,3);
   da1=(double)decode_gene(n,22,3);
   sa2=(double)decode_gene(n2,19,3);
   da2=(double)decode_gene(n2,22,3);
   rnd1=(double)random(1001)/1000.0;
   rnd2=(double)random(1001)/1000.0;
   attack1=(double)iatr[n][2]+sa1*20.0/7.0*rnd1+da1*20.0/7.0*rnd2;
   rnd1=(double)random(1001)/1000.0;
   rnd2=(double)random(1001)/1000.0;
   attack2=(double)iatr[n2][2]+sa2*20.0/7.0*rnd1+da2*20.0/7.0*rnd2;
   /* 减少内部能量 */
   La1=decode_gene(n,25,3);
   La2=decode_gene(n2,25,3);
   rnd1=(double)random(1001)/1000.0;
   iatr[n][2]=iatr[n][2]-(int)((double)La1*rnd1);
   rnd2=(double)random(1001)/1000.0;
   iatr[n2][2]=iatr[n2][2]-(int)((double)La2*rnd2);
   if(attack1>=attack2)                         /* 胜者: n 败者:n2 */
     iatr[n2][2]=iatr[n2][2]-40;
   else                                         /* 胜者: n2 败者:n */
     iatr[n][2]=iatr[n][2]-40;
   if(iatr[n][2]<=0) remove_life(n);
   if(iatr[n2][2]<=0) remove_life(n2);
   }

  void  act2_eat(n)                            /* 个体n获取行动范围内的食物 */
  int n;
  {
    int sft[8][2]={{1,0},{1,1},{0,1},{-1,1},
                  {-1,0},{-1,-1},{0,-1},{1,-1}};
  int x1,y1,x2,y2,n2,ef;
  int found,rndnum;
  x1=iatr[n][0];y1=iatr[n][1];
/*  获取食物位置(x2,y2)  */
  found=0;
  while(found==0)
  {
   rndnum=random(8);
   x2=x1+sft[rndnum][0];
   y2=y1+sft[rndnum][1];
   if(get_world(x2,y2)==3||get_world(x2,y2)==5)
   found=1;
   }
   /* 增加内部能量 */
   ef=decode_gene(n,28,4);  /* 食物吸取效率 */
   iatr[n][2]=iatr[n][2]+(int)(40.0*(50.0+(double)ef*50.0/15.0)/100.0);
   if(iatr[n][2]>100)  iatr[n][2]=100;
   /* 检查食物号n2  */
   found=0;n2=0;
   while(found==0)
   {
     if(fatr[n2][0]==x2 && fatr[n2][1]==y2 && fflg[n2]==1)
     found=1;  else n2++;
   }
   remove_food(n2);
   }

void act3_makechild(n)              /* 个体n与行动范围内的其他生物个体交配产生子个体 */
int n;
{
  int i,j,k,x,y,x2,y2,found,n2,trial;
  int x3,y3;
  double rnd;
  if(pop_size+1<=MAX_POP)
  {
    x=iatr[n][0];y=iatr[n][1];
    found=0;
    while(found==0)
    {
    x2=x+random(3)-1;
    y2=y+random(3)-1;
    if(x2!=x||y2!=y)
      if(get_world(x2,y2)==gene[n][0]+1);
      found=1;
    }
   /* 检查交配对象个体号n2  */
   found=0; n2=0;
   while(found==0)
   {
    if((iatr[n2][0]==x2 || iatr[n2][1]==y2) && iflg[n2]==1)
     found=1;   else n2++;
     if(n2>=pop_size-1) return;
   }
   /* 确定产生个体位置 */
   found=0;trial=0;
   while(found==0 && trial<50)
   {
   i=random(3)-1;j=random(3)-1;
   k=random(2);
   if(k==0)  {  x3=x+i;y3=y+j;}
   else      { x3=x2+i;y3=y2+j;}
   if(get_world(x3,y3)==0) found=1;
   trial++;
   }
   if(found==1)
   {
   /* 个体 n与个体 n2产生子个体 */
   pop_size++;
   /*  均匀交叉 */
   uni_crossover(gene,n,n2,pop_size-1,0.5,G_LENGTH);
   /*  变异    */
   for(i=1;i<G_LENGTH;i++)
   {
        rnd=random(10001)/10000.0;
        if(rnd<=MUTATION)
                if(gene[pop_size-1]==1)
                   gene[pop_size-1]=0;
                else  gene[pop_size-1]=1;
   }
   /* 交配后父个体能量减少  */
   iatr[n][2]=iatr[n][2]-45;
   if(iatr[n][2]<=0)  remove_life(n);
   iatr[n2][2]=iatr[n2][2]-45;
   if(iatr[n2][2]<=0)  remove_life(n2);
   /*  子个体属性输入  */
   iatr[pop_size-1][0]=x3;
   iatr[pop_size-1][1]=y3;
   iatr[pop_size-1][2]=100;
   iatr[pop_size-1][3]=0;
   iflg[pop_size-1]=1;
   /*  子个体画面表示 */
   world[x3][y3]=gene[pop_size-1][0]+1;
   g_disp_unit(x3,y3,gene[pop_size-1][0]+1);
   }
  }
}

void act_individual(n)              /* 为行动范围内的其他生物和食物决定行动 */
int n;
{
   int i,j,k,pattern,action,cr,ca;
   int act[3];                      /* act[0]:攻击 act[1]:获取食物 act[2]:交配 */
   int pat[6][3]={{1,2,3},{1,3,2},{2,1,3},
                  {3,1,2},{2,3,1},{3,2,1}};
                                    /*  pat:行动优先顺序 {攻击，获取食物，交配}  */
   int sp;
   double rnd;
   sp=decode_gene(n,0,1)+1;
   for(i=0;i<3;i++) act=0;
   for(i=-1;i<=1;i++)
     for(j=-1;j<=1;j++)
     {
       if(i!=0||j!=0)
       {
         k=get_world(iatr[n][0]+j,iatr[n][1]+i);
         if(k==1||k==2)  act[0]=1;
         if(k==3||k==5)  act[1]=1;
         if(k==sp)       act[2]=1;
         }
       }
       cr=decode_gene(n,16,3);
       rnd=(double)random(10001)/10000.0;
       if(rnd<=(double)cr/7.0)
       {
         action=random(3);
         while(act[action]==0)
         action=random(3);
         }
       else
       {
       ca=decode_gene(n,13,3);                 /* ca行动特点 */
       if(ca<3)  pattern=0;else  pattern=ca-2;
       /* 基本行动模式pattern 0-5 */
       i=0;
       action=pat[pattern]-1;
       while( act[action]==0)
       {
         i++;
         action=pat[pattern]-1;
         }
        }
     switch(action+1)
     {
        case 1:  act1_attack(n);break;
        case 2:  act2_eat(n);break;
        case 3:  act3_makechild(n);
     }
   }

void init_flags()                      /* 状态标志初始化 */
   {
   int i;
     for(i=0;i<pop_size;i++)  iflg=1;
     for(i=0;i<food_size;i++)  fflg=1;
   }

void  act_lives()                     /*  改变状态(移动或行动)  */
{
   int i,j,k,x,y,move,a;
   for(i=0;i<pop_size;i++)
   {
     if(iflg==1)
     {
       move=1;
       for(j=-1;j<=1;j++)
        for(k=-1;k<=1;k++)
        {
          if(j!=0||k!=0)
          {
            a=get_world(iatr[0]+k,iatr[1]+j);
            if(a==1||a==2||a==3||a==5)
            move=0;
            }
        }
       if(move==1)
         move_individual(i);
       else
         act_individual(i);
     }
   }
}

void  increase_age()              /* 个体年龄增1  */
{
  int i,j,s;
  for(i=0;i<pop_size;i++)
  {
    if(iflg==1)
    {
      j=decode_gene(i,1,4);
      s=SL_MIN+j;
      iatr[3]++;
      if(iatr[3]>s)
      remove_life(i);
      }
    }
  }

void  increase_frsh()            /* 食物新鲜度增1  */
{
  int i;
  for(i=0;i<food_size;i++)
    if(fflg==1)
    {
     fatr[3]++;
     if((fatr[2]==0 && fatr[3]>TL1)||
        (fatr[2]==1 && fatr[3]>TL2))
        remove_food(i);
        }
  }

void gabage_col()             /* 死去个体及消减食物清除*/
{
int i,j;
int new_pop,new_food;
   /* 检查食物 */
new_food=0;
for(i=0;i<food_size;i++)
   if(fflg==1)
   {
   new_food++;
   for(j=0;j<4;j++)
      fatr[new_food-1][j]=fatr[j];
   }
   food_size=new_food;
  /* 检查个体 */
   new_pop=0;
   for(i=0;i<pop_size;i++)
     if(iflg==1)
     {
       new_pop++;
       /* 遗传基因复制  */
       for(j=0;j<G_LENGTH;j++)
         gene[new_pop-1][j]=gene[j];
       /* 属性复制  */
       for(j=0;j<4;j++)
         iatr[new_pop-1][j]=iatr[j];
      }
     pop_size=new_pop;
  }

  void  make_foods()                 /* 产生一代中植物性食物  */
  {
  int i,x,y;
  for(i=0;i<NEWFOODS;i++)
  {
    if(food_size+1<=MAX_FOOD)
    {
      food_size++;
      find_empty(&x,&y);
      fatr[food_size-1][0]=x;
      fatr[food_size-1][1]=y;
      fatr[food_size-1][2]=0;        /* 植物性 */
      fatr[food_size-1][3]=0;
      fflg[food_size-1]=1;
      world[x][y]=3;
      g_disp_unit(x,y,3);
     }
   }
  }

  void  calc_population(n1,n2)  /* 计算生物1和2 的个体数 */
  int *n1,*n2;
  {
    int i,p1,p2;
    p1=0;p2=0;
    if(pop_size>0)
      for(i=0;i<pop_size;i++)
        if(gene[0]==0)  p1++; else p2++;
        *n1=p1;
        *n2=p2;
  }

main()    /* 主程序  */
{
int i,work;
int n1,n2,n1old,n2old;
char choice[2];
randomize();
/* 图形界面初始化 */
g_init();
settextstyle(0,0,4);
gprintf(220,20,4,0,"ALIFE");
setcolor(9);
disp_hz24("基于遗传算法的人工生命模拟",150,60,25);
setcolor(15);
disp_hz16("人工环境及生物分布",10,160,20);
disp_hz16("1:随机产生  2: 读文件产生 ==>",10,190,20);
gscanf(300,190,15,1,4,"%s",choice);
work=atoi(choice);
if(work==2)  load_world_file();else make_world();
make_lives_and_foods();
/*状态初始化 */
init_flags();
/*计算个体数 */
calc_population(&n1old,&n2old);
/*生成初始画面*/
g_init_frames();
/*虚拟世界画面*/
g_draw_world();
/* 显示初始图形 */
g_init_graph();
for(i=1;i<121;i++)
{
  /*状态初始化 */
  init_flags();
  /* 改变状态(移动或行动)  */
  act_lives();
  /* 个体年龄增加  */
  increase_age();
  /* 食物新鲜度增加 */
  increase_frsh();
  /*死去个体及消减食物清除*/
  gabage_col();
  /*产生新的食物 */
  make_foods();
/* 求生物1和2 的个体数 */
  calc_population(&n1,&n2);
  /* 个体数变化的图形更新  */
  g_plot_population(i,n1,n2,n1old,n2old);
  n1old=n1;n2old=n2;
/* 显示最佳遗传基因  */
  g_disp_genotype();
   }
  setcolor(9);
  disp_hz16("回车键结束",10,430,20);
  getch();
}  



蚂蚁算法
 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。
 它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要
多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，
其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可
能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不
可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。

然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁
干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实
只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的
行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明：

1、范围：
蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，
并且能移动的距离也在这个范围之内。
2、环境：
蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下
的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让
信息素消失。
3、觅食规则：
在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点
的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。
蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。
4、移动规则： 
每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，
并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点
已经在最近走过了，它就会尽量避开。
5、避障规则：
如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。 
7、播撒信息素规则：
每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。

根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁
之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的
蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。

说了这么多，蚂蚁究竟是怎么找到食物的呢？
在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，
尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机
固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒
子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有
新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向
正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。
当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。

蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里
的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多
（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次
的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有
更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，
最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？
这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果
能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。

引申:
跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的
简单行为规则，而这些规则综合起来具有下面两个方面的特点：
1、多样性
2、正反馈
多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以
把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威
体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。

引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证
了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，
它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行
为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。
既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？
多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正
反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，
之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！

参数说明：
最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时
间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。
错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。
速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。
记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统
运行速度就慢，越小则蚂蚁越容易原地转圈。

-----例子-----
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><HEAD>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
<title>蚁群算法js版</title>
<style>
.ant{
position:absolute;
background-color:#000000;
overflow:hidden;
width:2px;
height:2px;
}
.food{
position:absolute;
background-color:#0000ff;
overflow:hidden;
width:2px;
height:2px;
}
.nest{
position:absolute;
background-color:#ff0000;
overflow:hidden;
width:2px;
height:2px;
}
</style>
<script type="text/JavaScript">
//============================
//系统参数初始化
//----------------------------
//生命体数量与轨迹长度
Unit=10;Path=30;
//生命体速度上下限
v0=2;vM=10;
//生命体加速度变化范围
Kr=0.1;Kv=0.1*(vM-v0);
//生命体运动范围
x0=0;xM=document.documentElement.clientWidth;
y0=0;yM=document.documentElement.clientHeight;
//生命体出生地(巢穴)
xi0=x0+(xM-x0)*Math.random();
yi0=y0+(yM-y0)*Math.random();
str0='<div class="ant" style="left:'+xi0+';top:'+yi0+';"></div>';
//食物所在地
xf=x0+(xM-x0)*Math.random();
yf=y0+(yM-y0)*Math.random();
//气味感知范围
R_2=5*5;
//============================
var r=new Array();
var v=new Array();
var dr=new Array();
var dv=new Array();
var x=new Array();
var y=new Array();
var life=new Array();

//单击暂停
var xi0,yi0,xf,yf;
var Time0,str0;
window.status='pause';
function document.onclick(){
        if(window.status=='pause'){
                window.status=0;
                nest.style.left=xi0;
                nest.style.top=yi0;
                food.style.left=xf;
                food.style.top=yf;
                //测试初始化时间用
                Time0=(new Date()).getTime();
                init(0);
        }else{
                window.status='pause';
        }
}
//窗口大小调整后刷新页面以调整系统参数
function window.onresize(){
//        window.location.href=document.location;
}
//初始化函数
function init(i){
        if(window.status!='pause'&&i<Unit){
                if(!life){
                        document.body.appendChild(life=document.createElement(str0));
                        x=xi0;
                        y=yi0;
                        r=Math.random();
                        v=1/Math.random();
                        dr=Kr*Math.random();
                        dv=Kv*Math.random();
                }
                Move(i);
                window.status=i+1;
                setTimeout('init('+(i+1)+')',i);
//        }else{
//                alert('生成耗时：'+((new Date()).getTime()-Time0)+'ms');
        }
}
//运动函数
Total=Unit*Path;
P2=2*Math.PI;
function Move(i){
        if(window.status!='pause'){
                k=i%Unit;
                X=x[k];
                Y=y[k];
                R=r[k];
                V=v[k];                
                if(!life){
                        str='<div class="ant" style="left:'+X+';top:'+Y+';"></div>';
                        document.body.appendChild(life=document.createElement(str));
                }
                obj=life;
                R+=dr[k]*(2*Math.random()-1);
                V+=dv[k]*(2*Math.random()-1);
                X+=Math.sin(P2*R)*V;
                Y+=Math.cos(P2*R)*V;
                //遇到食物原路返回并减小角度变化
                distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf);
                if(distance<R_2){
                        R+=0.5;
                        r/=2;
                        v*=2;
                }
                distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0);
                if(distance<R_2){
                        R+=0.5;
                        r/=2;
                        v*=2;
                }
                /*----------------------------------
                /*================================*/
                //碰撞边界反弹
                R=(X<x0||X>xM)?-R:R;
                R=(Y<y0||Y>yM)?0.5-R:R;
                X=x[k]+Math.sin(P2*R)*V;
                Y=y[k]+Math.cos(P2*R)*V;
                /*================================*/
                //溢出边界重生(类似流星效果)
                if(X<x0||X>xM||Y<y0||Y>yM){
                        X=xi0;
                        Y=yi0;
                }
                /*----------------------------------
                /*================================*/
                //边界限制
                x[k]=X=(X<x0)?x0:(X>xM)?xM-2:X;
                y[k]=Y=(Y<y0)?y0:(Y>yM)?yM-2:Y;
                r[k]=R>1?R-1:R<0?R+1:R;
                v[k]=V=(V<v0)?v0:((V<vM)?V:vM);
                /*================================*/
                obj.style.left=x[k]=X;
                obj.style.top=y[k]=Y;
                setTimeout('Move('+(i+Unit)%Total+')',Unit);
        }
}

//根据浏览器自动加载动画
switch(navigator.appName.toLowerCase()){
        case "netscape":
                window.addEventListener("load",document.onclick,false);
        break;
        case "microsoft internet explorer":
        default:
                window.attachEvent("onload",document.onclick);
        break;
}
</script>
</head>
<body scroll="no">
<div id="food" class="food"></div>
<div id="nest" class="nest"></div>
</body>
</html> 


跳窗算法
跳窗(Jumping Window)算法的基本思想是限制在窗口时间T内进入网络的信元数量m。它将时间划分为一个个连续的固定长
度的时间间隔T作为时间窗口，网络在一个时间窗口内最多只能接受m个信元，其余信元被丢弃或被打上违约标志。因此，
实际进入网络的信元流量不超过m/T。在m = 1, T = 1/a时，跳窗算法就是漏桶算法，这里a是漏桶中信元的流出速率。
　　跳窗算法的关键是选取m和T。选取时，应注意以下问题: 
　　1.T如果太大，会使控制的实时性降低，导致漏判。
　　2 T如果太小，会对履约的信元进行错判。例如，对于周期性信息源，T小于一个周期便会出现错判。
　　3.m/T不能小于业务的平均信元速率，否则，业务无法被正常传递。  


滑窗算法
与跳窗算法类似，滑窗(Moving Window)算法也是通过限制各个时间窗口内所能接收的最大信元数对业务量进行控制。
区别是，在滑窗算法中，时间窗口不是向前跳，而是每过一个信元时间向前滑动一次，滑动的长度是一个信元的时间。 
以上是几种UPC算法。信元一旦被UPC判定是违约的，就要对其采取管制措施。主要措施包括：
　　1． 丢弃违约信元甚至所在连接上的所有信元。这是对违约信元及其连接的最直接、最严厉的惩罚。在有些场合下，
这种措施不太合理。因为用现有的业务量参数难以对业务特征进行完全准确的描述，而且在呼叫建立阶段这些参数常常难以确定。
　　2． 将违约信元打上标记（将信元头中的CLP置1），交换节点在网络发生拥塞时丢弃这些信元。显然，这对违约信元的
处理要宽松一些。但它要求网络能够区分标记和未标记信元。会为违约者盗用资源提供机会。 
　　3． 延迟违约信元来平滑业务特性。这种方法需要很大的缓冲区，并会增加时延。同样也会为违约者盗用资源提供机会。 
　　4． 通知源端降低发送速率。这种方法的缺点是反应迟缓，难以及时保护履约连接的QoS。  


自打印算法
自打印算法是指在程序运行中，不读取任何额外的信息，仅使用程序代码中携带的功能和信息，将程序代码本身打印输出。
一个完整的自打印程序至少保含两部分：信息的描述和执行体。这两者互相表达。在描述部分，用字符串来存储执行部分的代码。而执行体的代码则打印这个描述字符串。通常为了完整输出程序代码，要在执行体内为描述字符串再拼接一些修饰性的内容，这些内容被看作是执行体的一部分。而代码的打印也要打印为两部分，才能将描述文本打印为一个新的描述文本和一个新的执行体。
这个过程根据不同的编程语言，可以通过一些技巧进行简化，例如《高效程序的奥秘》一书中，演示了这样一个C语言版的自打印程序：

main(a)
{
　printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);
}

这段程序巧妙的利用了printf的格式化解析，将程序代码编写的简洁而清晰。
如果自打印算法只能打印自身代码，那么它只是一个玩具而已，实际上只要耐心操作字符串，我们可以在自打印中携带其它代码。我们看如下的Python代码：
s = '''def PrintSelf(Input):
    print "s = " + chr(047) + chr(047) + chr(047) + Input + chr(047) + chr(047) + chr(047) + "\\n\\n" + Input + "\\n\\n" + PrintSelf(s)'''

def PrintSelf(Input):
    print "s = " + chr(047) + chr(047) + chr(047) + Input + chr(047) + chr(047) + chr(047) + "\n\n" + Input + "\n\n" + "PrintSelf(s)"

PrintSelf(s)
这也是一个自打印程序，它的格式写的很松散，这就方便了我们在里面添加新代码：
s = ''' f=open("c:/txt.txt")
def PrintSelf(Input):
    print "s = " + chr(047) + chr(047) + chr(047) + Input + chr(047) + chr(047) + chr(047) + "\\n\\n" + Input + "\\n\\n" + print "Hello World" + PrintSelf(s)'''

f=open("c:/txt.txt")
def PrintSelf(Input):
    print "s = " + chr(047) + chr(047) + chr(047) + Input + chr(047) + chr(047) + chr(047) + "\n\n" + Input + "\n\n" + "PrintSelf(s)"

PrintSelf(s)

执行这个程序，我们就可以在打印时打开一个文件对象，如果按着这个思路，我们还可以在文本里面写入程序代码本身；使用exec函数，还可以使程序反复执行。

当然，各种语言的字符串操作能力和逻辑结构的限制不同，实现自打印的方式也会有区别，其代码的风味也各有不同。本次比赛的参赛者使用了多种语言，包括C++、Java、C#、Python等等，很遗憾我们没有看到以字符串操作能力闻名的Perl语言作品，想来应该也是独具一格的。大多数参赛者都正确的实现了自打印算法，但是其中的代码长度大相径庭，这其中除了技巧运用的差异，还有语言本身的限制。

本次比赛的优胜者施凡先生提供了若干种语言版本，其中的Python版本当之无愧的称为本次比赛的最佳作品：


Print (lambda s:s.replace(chr(042),chr(047))%s)('print (lambda s:s.replace(chr(042), chr(047))%%s)("%s")')

这段代码紧凑精巧，充分体现了自打印算法的精妙之处。对lambda的运用也恰到好处。Python的作者Guido van Rossum准备取消lambda，如果他有机会读到施凡先生的代码，不知是否会改变主意。

自打印算法很有趣味性，它体现了高超的微观技巧；但是另一方面，自打印也有其形而上的哲学味道。它在数学高度上演示了如何构造一个可以自复制、自表达的系统。事实上，自打印程序中的描述文本，正对应了细胞生物的染色体，自打印算法，可以看作是细胞生命的一个数学抽象。前面我们看到，在自打印程序中实际上可以携带其它信息，这说明这个模型可以完成“繁殖”之外的功能。自打印算法颠覆了“神创造生命”的神权至上理论。生化领域的科学家们一路从尿素、氨基酸、胰岛素走来，艰难而执着的向构造细胞生命迈进，而自打印算法为这条看来遥遥无尽的通天之路添加了数学的路标。  


pagerank
 通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算，PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量，而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。
    此外，PageRank 还会评估每个投票网页的重要性，因为某些网页的投票被认为具有较高的价值，这样，它所链接的网页就能获得较高的价值。重要网页获得的 PageRank（网页排名）较高，从而显示在搜索结果的顶部。Google 技术使用网上反馈的综合信息来确定某个网页的重要性。搜索结果没有人工干预或操纵，这也是为什么 Google 会成为一个广受用户信赖、不受付费排名影响且公正客观的信息来源。
－－－－－－－－－－－－－－－
其实简单说就是民主表决。打个比方，假如我们要找李开复博士，有一百个人举手说自己是李开复。那么谁是真的呢？也许有好几个真的，但即使如此谁又是大家真正想找的呢？:-) 如果大家都说在 Google 公司的那个是真的，那么他就是真的。
在互联网上，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。这就是 Page Rank 的核心思想。 当然 Google 的 Page Rank 算法实际上要复杂得多。比如说，对来自不同网页的链接对待不同，本身网页排名高的链接更可靠，于是给这些链接予较大的权重。Page Rank 考虑了这个因素，可是现在问题又来了，计算搜索结果的网页排名过程中需要用到网页本身的排名，这不成了先有鸡还是先有蛋的问题了吗？
Google 的两个创始人拉里•佩奇 （Larry Page ）和谢尔盖•布林 (Sergey Brin) 把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。值得一提的事，这种算法是完全没有任何人工干预的。
理论问题解决了，又遇到实际问题。因为互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。拉里和谢尔盖两人利用稀疏矩阵计算的技巧，大大的简化了计算量，并实现了这个网页排名算法。今天 Google 的工程师把这个算法移植到并行的计算机中，进一步缩短了计算时间，使网页更新的周期比以前短了许多。
我来 Google 后，拉里 (Larry) 在和我们几个新员工座谈时，讲起他当年和谢尔盖(Sergey) 是怎么想到网页排名算法的。他说："当时我们觉得整个互联网就像一张大的图 （Graph)，每个网站就像一个节点，而每个网页的链接就像一个弧。我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做个博士论文。" 他和谢尔盖就这样发明了 Page Rank 的算法。
网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系。 
今天，Google 搜索引擎比最初复杂、完善了许多。但是网页排名在 Google 所有算法中依然是至关重要的。在学术界, 这个算法被公认为是文献检索中最大的贡献之一，并且被很多大学引入了信息检索课程 (Information Retrieval) 的教程。  


B-tree
B-tree索引是数据库中存取和查找文件(称为记录或键值)的一种方法。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。

    一个B-tree的典型例子就是硬盘中的结点。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。  

kmp算法
一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。
完全掌握KMP算法思想


      学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。 
      如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解KMP算法。(小弟正在备战考研，为了节省时间，很多课本上的话我都在此省略了，以后一定补上。)

      严老的《数据结构》79页讲了基本的匹配方法，这是基础。先把这个搞懂了。
      80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。
我们继续往下看：
现在讨论一般情况。
假设 主串：s: ‘s(1)  s(2)  s(3) ……s(n)’ ;   模式串 ：p: ‘p(1)  p(2)  p(3)…..p(m)’
把课本上的这一段看完后，继续

现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较

此时，s(i)≠p(j),  有

主串：               S(1)……  s(i-j+1)…… s(i-1)   s(i) ………….
                                || (相配)   ||       ≠(失配)
匹配串：                        P(1) …….  p(j-1)   p(j) 

由此，我们得到关系式
          ‘p(1)  p(2)  p(3)…..p(j-1)’   =    ’ s(i-j+1)……s(i-1)’

由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在  k’>k  满足下列关系式：(k<j),
          ‘p(1)  p(2)  p(3)…..p(k-1)’   =    ’ s(i-k+1)s(i-k+2)……s(i-1)’

即：

主串：        S(1)……s(i-k +1) s(i-k +2) ……s(i-1)     s(i) ………….
                        || (相配)  ||           ||       ?(有待比较)
匹配串：                P(1)      p(2)    …… p(k-1)    p(k)

现在我们把前面总结的关系综合一下

有：

S(1)…s(i-j +1)…  s(i-k +1) s(i-k +2)  ……    s(i-1)     s(i) ……
           || (相配)  ||         ||               ||         ≠(失配)
           P(1) ……p(j-k+1)   p(j-k+2)  …....   p(j-1)    p(j) 
                      || (相配)  ||               ||          ?(有待比较)
                      P(1)       p(2)    …….    p(k-1)      p(k)

由上，我们得到关系：
‘p(1)  p(2)  p(3)…..p(k-1)’   =    ’ s(j-k+1)s(j-k+2)……s(j-1)’


接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)

K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。
课本83页不是有个例子吗？就是  图4.6
你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。
然后找几道练习题好好练练，一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了，再回去看它是怎么推出来的，如果还看不懂，就继续做练习，做完练习再看。相信自己！！！

附：

KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

inline void NEXT(const string& T,vector<int>& next)
{
    //按模式串生成vector,next(T.size())   
    next[0]=-1;            
    for(int i=1;i<T.size();i++ ){
        int j=next[i-1];
        while(T!=T[j+1]&& j>=0 )
         j=next[j] ;  //递推计算
        if(T==T[j+1])next=j+1; 
        else next=0;  //
    }   
} 
inline string::size_type COUNT_KMP(const string&  S,
                    const string&  T)
{
    //利用模式串T的next函数求T在主串S中的个数count的KMP算法
    //其中T非空，
    vector<int> next(T.size());
    NEXT(T,next);
    string::size_type index,count=0;   
    for(index=0;index<S.size();++index){      
        int pos=0;
        string::size_type iter=index;
        while(pos<T.size() && iter<S.size()){
            if(S[iter]==T[pos]){
                ++iter;++pos;
            }
            else{
                if(pos==0)++iter;              
                else pos=next[pos-1]+1;
            }   
        }//while end
        if(pos==T.size()&&(iter-index)==T.size())++count;
    } //for end
    return count;
}
int main(int argc, char *argv[])
{
    string S="abaabcacabaabcacabaabcacabaabcacabaabcac";
    string T="ab";
    string::size_type count=COUNT_KMP(S,T);
    cout<<count<<endl;

  system("PAUSE");
  return 0;
}  


点灯游戏
 点灯游戏是一个十分有趣的智力游戏,他的规则是这样的:有一行N行N列的灯,开始时全部是灭的,
当你点击其中一盏灯是他的上下左右(若存在的话)状态全部改变,现在要求你在限定的时间内以最少
地步数,将全部的灯点亮. 
  现在,我们以某一盏灯为研究对象,显然,当此灯状态被改变奇数次后,灯被点亮.反之,被点击偶数次,
灯则维持原来的熄灭状态不变.而促使灯状态改变的事件不外乎其上下左右(若存在的话)被点击.
推而广之,只要所有的灯状态被改变奇数次,则可保证所有的灯全部被点亮.同时,应该,说明的是,
对每一盏灯来说,自身被点次奇数数与一次效果相同,这是因为,对每盏灯来说,被点一次后,再点偶数次,
自身他的上下左右(若存在的话)状态恢复原态.同样道理,自身被点偶数次,相当于没被点.故在最少步数
的限制下,每盏灯要么没被点,要么仅被点一次.
我们很容易想到,可以用枚举的方法来解决问题,以4行4列为例,  程序如下:
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"Conio.h"
main()
{ FILE *fp; 
int row=6;
int a[100]=,i,j,m,n,k,s,ss,sum;
        clrscr();
for(a[0]=0;a[0]<=1;a[0]++)
for(a[1]=0;a[1]<=1;a[1]++)
for(a[2]=0;a[2]<=1;a[2]++)        
for(a[3]=0;a[3]<=1;a[3]++)      
for(a[4]=0;a[4]<=1;a[4]++) 
for(a[5]=0;a[5]<=1;a[5]++)
.....
for(a[15]=0;a[15]<=1;a[15]++)
{ for(i=0;i<4;i++)
  for(j=0;j<4;j++)
{ m=(i-1)>=0?a[(i-1)*4+j]:0;
  n=(j-1)>=0?a[i*4+j-1]:0;
  p=(j+1)>=0?a[i*4+j+1]:0;
  q=(i+1)>=0?a[(i+1)*4+j]:0;
  s=m+n+p+q+a[i*4+j];
   if(s%2==0) break;
}
}

此算法的最大缺点是:循环次数太多,使N*N次,随着N次数地增加,执行时间加长.
为此又提出一种改进算法:
我们知道对每一盏灯而言,每盏灯的状态改变次数仅与其上下左右(若存在的话)和自身
被点次数有关.这样我们就可以对第一行利用枚举法.列出其所有的可能值,
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"Conio.h"
main()
{ FILE *fp; 
int row=6;
int a[100]=,i,j,m,n,k,s,ss,sum;
        clrscr();
for(a[0]=0;a[0]<=1;a[0]++)
for(a[1]=0;a[1]<=1;a[1]++)
for(a[2]=0;a[2]<=1;a[2]++)        
for(a[3]=0;a[3]<=1;a[3]++)      
for(a[4]=0;a[4]<=1;a[4]++) 
for(a[5]=0;a[5]<=1;a[5]++)
{ for(k=0;k<row;k++)
    for(i=1;i<row;i++)                     /* OUT 1  ROW */
     for(j=0;j<row;j++)
    {   s=a[(i-1)*row+j];            /* 上 */
    if(i-2>=0)  s+=a[(i-2)*row+j];           /*上上 */
    if(i-1>=0) { if(j-1>=0)   s+=a[(i-1)*row+j-1];   /*上左 */
                 if(j+1<row)  s+=a[(i-1)*row+j+1];   /*上右 */               
               }
        if(s<=1)          a[i*row+j]=1-s;               /*self */
        else if(s<=3)     a[i*row+j]=3-s;
        else              a[i*row+j]=1;  
    }         
       m=row-1;
     for(n=0;n<row;n++)                        /*Judge last row ok? */
   {   ss=a[m*row+n]+a[(m-1)*row+n];             /*上 self */
    if(n-1>=0)     ss+=a[m*row+n-1];           /*左 */
    if(n+1<row)    ss+=a[m*row+n+1];           /*右 */     
    if(ss%2==0) break;
   }
   if(n==row) {   printf("\n    OK !\n"); fputs("\n    OK !\n",fp);
                             sum=0;
                        for(i=0;i<n*n;i++)
                            {    sum+=a;
                          printf("%2d",a);   fprintf(fp,"%2d",a);
                             if((i+1)%n==0)        printf("\n"),fputs("\n",fp);
                          }  printf("点击次数:%2d.\n\n", sum);
                           fprintf(fp,"点击次数:%2d.\n\n", sum);
                                 getch();
              }
             
}   fclose(fp);
}  


退火算法
 Simulate Anneal Arithmetic (SAA,模拟退火算法)

模拟退火算法 

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 

1 . 模拟退火算法的模型 

模拟退火算法可以分解为解空间、目标函数和初始解三部分。 

模拟退火的基本思想: 

(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L 

(2) 对k=1，……，L做第(3)至第6步： 

(3) 产生新解S′ 

(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 

(5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解. 

(6) 如果满足终止条件则输出当前解作为最优解，结束程序。 

终止条件通常取为连续若干个新解都没有被接受时终止算法。 

(7) T逐渐减少，且T->0，然后转第2步。 

算法对应动态演示图： 

模拟退火算法新解的产生和接受可分为如下四个步骤： 

第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 

第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 

第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。 

第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 

模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 

2 模拟退火算法的简单应用 

作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i，j) i, j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。 

求解TSP的模拟退火算法模型可描述如下： 

解空间 解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2 ,……，wn)，并记wn+1= w1。初始解可选为(1，……，n) 

目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数： 

我们要求此代价函数的最小值。 

新解的产生 随机产生1和n之间的两相异数k和m，若k  (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 

变为： 

(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn). 

如果是k>m，则将 

(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 

变为： 

(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk). 

上述变换方法可简单说成是“逆转中间或者逆转两端”。 

也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。 

代价函数差 设将(w1, w2 ,……，wn)变换为(u1, u2 ,……，un), 则代价函数差为： 

根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序： 

Procedure TSPSA: 

begin 

init-of-T; { T为初始温度} 

S={1，……，n}; {S为初始值} 

termination=false; 

while termination=false 

begin 

for i=1 to L do 

begin 

generate(S′form S); { 从当前回路S产生新回路S′} 

Δt:=f(S′))-f(S);{f(S)为路径总长} 

IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1]) 

S=S′; 

IF the-halt-condition-is-TRUE THEN 

termination=true; 

End; 

T_lower; 

End; 

End 

模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 

3 模拟退火算法的参数控制问题 

模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点： 

(1) 温度T的初始值设置问题。 

温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 

(2) 退火速度问题。 

模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。 

(3) 温度管理问题。 

温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式： 

T(t+1)＝k×T(t) 

式中k为正的略小于1.00的常数，t为降温的次数  


快速排序
 快速排序 Quick Sort

我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。

下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。

算法的基本思想

快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序（比如用前述的冒泡、选择、插入排序均可），否则分三步处理：

分解(Divide)：将待排序列L[p..r]划分为两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。具体可通过这样的途径实现：在序列L[p..r]中选择数据元素L[q]，经比较和移动后，L[q]将处于L[p..r]中间的适当位置，使得数据元素L[q]的值小于L[q+1..r]中任一元素的值。 

递归求解(Conquer)：通过递归调用快速排序算法，分别对L[p..q]和L[q+1..r]进行排序。 

合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序，即自然合并。 

这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。


快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为"分区交换排序"。
  在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成"{左子序列}K{右子序列}"。再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。
  分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：例如，可取左边第1个元素为分界点、取中点A[（left+right）/2]为分界点、或选取最大和最小值的平均值为分界点等。  


算法复杂度
 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 

1、时间复杂度 

（1）时间频度 

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 

（2）时间复杂度 

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。 

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 

按数量级递增排列，常见的时间复杂度有： 

常数阶O(1),对数阶O(log2n),线性阶O(n), 

线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， 

k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 

2、空间复杂度 

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: 

S(n)=O(f(n)) 

我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。  


des算法
 DES算法是一种对称加密机制，由IBM为美国政府于70年代开发。
其入口参数有三个:key、data、mode。 key为加密解密使用的密钥，data为加密解密的数据，mode为其工作模式。当模式为加密模式时，key用于对数据加密，当模式为解密模式时，key用于对数据解密。
实际运用中，密钥只用到了64位中的56位，这样才具有高的安全性。  


深度优先搜索
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。优点是能遍历一个Web 站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。

(进化论密码按:由于以上一段描述本人不能看懂,所以暂时保留之.)

事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.

举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C,D),则我们可能得到如下的一个访问过程:A->B->E(没有路了!回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束).

  B--E
/
A-C--F
\     >H
  D--G

简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量.深度优先搜索可以从多点发起.如果将每个节点在深度优先搜索过程中的"结束时间"排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的"拓扑排序",即topological sort.

当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索 (BFS).状态（state):状态是制问题求解过程中每一步的状况。
算符（operater）算符是把问题从一种状态变换到另一种状态的方法代号。算符的屈指范围就是搜索的范围。（一般设为局部变量)。
节点（node）:用来表明状态特征及相关信息。  


爬山算法
爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 

爬山算法一般存在以下问题： 

局部最大 
高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 
山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。  


自然合并排序
自然合并排序是合并排序算法的一种改进.
自然合并排序:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段有{4,8},{3,7},{1,5,6},.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).继续合并相邻排好序的子数组段,直至整个数组已排好序.
 
贪心法
 贪心法(Greedy algorithm)是一种在每一步选择中都采取在当前状态下最好/优的选择，从而希望导致结果是最好/优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市， 那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
 
广度优先搜索
广度优先搜索,即BFS(Breadth First Search),常常与深度优先搜索并列提及。这是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的近邻加入搜索队列（而深度优先搜索则是栈），循环搜索过程直到队列为空。

仍以深度优先搜索中的图为例（但是希望各位不要产生深搜和广搜只能用于无向图的错觉）：

  B--E
/
A-C--F
\    >H
  D--G

如上图(H是和F,G相连的，空格被吃掉)，从A点发起一次广度优先搜索，则可以得到如下搜索结果：

当前点             搜索队列
A                  初始队列为空，具体编码可以灵活掌握。
                   BCD
B                  CD
                   CDE
C                  DE
                   DEF
D                  EF
                   EFG
E                  FG
                   FG
F                  G
                   GH
G                  H
                   H
H                  队列空。

应用：无权最短路。
 

HillTop
 HillTop 同样是一项搜索引擎结果排序的专利，是Google的一个工程师Bharat在2001年获得的专利。Google的排序规则经常在变化，但变化最大的一次也就是基于HillTop算法进行了优化。HillTop究竟原理如何，值得Google如此青睐？

其实HillTop算法的指导思想和PageRank的是一致的，都是通过网页被链接的数量和质量来确定搜索结果的排序权重。但HillTop认为只计算来自具有相同主题的相关文档链接对于搜索者的价值会更大：即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高。如果网站是介绍“服装”的，有10个链接都是从“服装”相关的网站链接过来，那这10个链接比另外10个从“电器”相关网站链接过来的贡献要大。Bharat称这种对主题有影响的文档为“专家”文档，从这些专家文档页面到目标文档的链接决定了被链接网页“权重得分”的主要部分。 

与PageRank结合HillTop算法确定网页与搜索关键词的匹配程度的基本排序过程取代了过分依靠PageRank的值去寻找那些权威页面的方法。这对于两个具有同样主题而且PR相近的网页排序过程中， HillTop算法就显得非常的重要了。HillTop同时也避免了许多想通过增加许多无效链接来提高网页PageRank值的做弊方法。

HillTop算法的指导思想和PageRank是一致的，即都通过反相链接的数量和质量来确定搜索结果的排序权重。但HillTop认为只计算来自具有相同主题的相关文档链接对于搜索者的价值会更大：即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高。在1999与2000年，当这个算法被Bharat与其他Google开发人员开发出来的时候，他们称这种对主题有影响的文档为“专家”文档，而只有从这些专家文档页面到目标文档的链接决定了被链接网页“权重得分”的主要部分。 

与PageRank结合HillTop算法确定网页与搜索关键词的匹配程度的基本排序过程取代了过份依靠PageRank的值去寻找那些权威页面的方法。这对于两个具有同样主题而且PR相近的网页排序过程中：HillTop算法就显得非常的重要了。 

Google最早利用HillTop算法去定义相关网站：一个网站与另一个网站的相关性，实际上，HillTop算法在Google也中作为一个识别跨站点的链接交换干扰(spam)与识别相似链接的技术。HillTop算法要求：如果有两个以上相关主题的网站链接到你的网站，那么你的网站在搜索结果中出现的机会会更大，如果HillTop算法不查找到最少两个相关性的网站，那么搜索返回的结果的机会绝对是0。

HillTop算法实际上是拒绝了部分通过随意交换链接的方法来扰乱Google的排名规则而得到较好排名的做法，而在HillTop的论文中也提到很多关于识别“网站链接交换联盟”的设计：如根据IPv4地址的头3段，根据域名的别名推测：example.com = example.com.cn； 

PR值对于搜索关键词的匹配度作用不大：因为在很多包含相应关键词的非相关主题的网站具有很高的PR值。这就是Google在HillTop算法中尽量避免的东西：应该尽其所能去列出与搜索关键词相关的结果。 

总得看来，从过去到今天，很多搜索引擎停止了那种只使用一种有价值的算法去决定排名的做法。如：meta keyword标签等。这只是一个开始，Google在第一步已经完全忽略html header中的meta标签了。与不可见的meta标签相比，一个网站的可视部分使用干扰技术较在meta使用的要少，因为可视部分毕竟还要面对大部分的实际的访问者。

基于“专家”文档的HillTop算法最大的难点是第一次“专家文档”的筛选，从目前的观察来看：Google显然首先给了教育(.edu)，政府(.gov)和非盈利组织(.org)站点很高的优先级。在运行时：Google会在庞大的内存里储存搜索频率比较高的关键词的索引，以备搜索者在短期内继续用同样的关键字短语等进行搜索。这些高频关键词还有另外一种作用，在“佛罗里达”更新之前很多人已经注意到的了：含有那些突增的搜索关键字的网站会得到较快的更新频率。如关于：\"SARS"，每天的搜索次数数以百万计：Google就会优先对与这个主题有关的网站进行更新。 

回头看一下以前每个月的“Google Dance”，也能得出以下的结论：Google也明显地为一个关键词给予一个随机的“权重”，动态的根据关键词查询统计发现这些热门关键词，然后基于HillTop算法面向主题地找到这些含有热门关键词的网页，让这些网页作为相应关键词的“专家”文档，针对这些索引入口保持比较高的更新频率：这点显然对于应对突发事件非常有效。而那些含有查询频率比较低的关键词所对应的网页可能要1月才更新一次。简单的说就是：Google会根据主题的热门程度动态调整相应网站的索引的强度。而Google中文用户在总体用户中的比例与Google索引的中文网页在索引的总体网页中的比例，从某种程度上说，也是有一定关系的。  



MPEG
更新:
(MPEG的全名为[Moving Pictures Experts Group]，中文译名是动态图像专家组。MPEG标准主要有以下五个，MPEG-1、MPEG-2、MPEG-4、MPEG-7及MPEG-21等。该专家组建于1988年，专门负责为CD建立视频和音频标准，而成员都是为视频、音频及系统领域的技术专家。及后，他们成功将声音和影像的记录脱离了传统的模拟方式，建立了ISO/IEC1172压缩编码标准，并制定出MPEG-格式，令视听传播方面进入了数码化时代。因此，大家现时泛指的MPEG-X版本，就是由ISO(International Organization for Standardization)所制定而发布的视频、音频、数据的压缩标准。)

MPEG标准的视频压缩编码技术主要利用了具有运动补偿的帧间压缩编码技术以减小时间冗余度，利用DCT技术以减小图象的空间冗余度，利用熵编码则在信息表示方面减小了统计冗余度。这几种技术的综合运用，大大增强了压缩性能。 

MPEG-1标准于1992年正式出版，标准的编号为ISO/IEC11172，其标题为“码率约为1.5Mb/s用于数字存贮媒体活动图象及其伴音的编码”。 

MPEG-2标准于1994年公布，包括编号为13818-1系统部分、编号为13818-2的视频部分、编号为13818-3的音频部分及编号为13818-4的符合性测试部分。 

MPEG-2编码标准希望囊括数字电视、图象通信各领域的编码标准，MPEG-2按压缩比大小的不同分成五个档次(profile)，每一个档次又按图象清晰度的不同分成四种图象格式，或称为级别(level)。五个档次四种级别共有20种组合，但实际应用中有些组合不太可能出现，较常用的是11种组合。这11种组合分别应用在不同的场合，如MP@ML(主档次与主级别)用在具有演播室质量标准清晰度电视SDTV中，美国HDTV大联盟采用MP@HL(主档次及高级别)。 

MPEG-4是基于内容的压缩编码标准。 

MPEG-7是“多媒体内容描述接口标准”。 

MPEG-21是有关多媒体框架的协议。

补充如下:
常见谬误
x﹕MPEG-4等如DIVX
*﹕不少人都以为DIVX即是MPEG-4，但其实DIVX是将影像部分以MPEG-4来压缩、音效部分以MP3压缩处理，再以AVI档格式存在的制成品，故档案较MPEG-2小，而画质表现就介乎MPEG-1与MPEG-2之间。

x﹕MP3即是MPEG-3
*﹕正如前述，MPEG-3只不过是被放弃的一种压缩技术，至于大家熟悉的MP3其实是MPEG-1 Layer 3的音频数据压缩技术，简称MP3。
    
全新压缩理念
至于MPEG-4的出现是由于MPEG-1和MPEG-2的压缩技术，不能将它放在网络上作为影音资料传递之用，所以MPEG-4不再是采用每张画面压缩的方式，而是采用了全新的压缩理念。先将画面上的静态对象统一制定规范标准，例如文字、背景、图形等，然后再以动态对象作基础的方式将画面压缩，务求以最少数据获得最佳的画质，并将之作为网络上传送之用。
此外，值得一提的是，继MPEG-4后，将会进入更先进的MPEG-7年代。这项崭新技术已非一种压缩编码方法，而是一种多媒体内容描述接口(Multimedia Content Description Interface)，能快速搜寻不同类型的多媒体材料，对于将来要面对日渐庞大的图像、声音的管理有重大帮助。
更新：
浅谈MPEG-4国际标准

作者：honey

浅谈MPEG-4国际标准

一、概述

     MPEG(Moving Pictures Experts Group,运动图片专家组)是在ISO(国际标准化组织)和IEC(国际电工委员会)内运作的一个工作组。自从1988年开始活动以来,MPEG已经编制了ISO /IEC11172(通常所说的MPEG-1)和ISO/IEC 13818(通常所说的MPEG-2)国际标准,其中包括用于服务器和网络会话的标准协议DSM-CC(Digital storage media command and control,数字存储媒体命令与控制)。

     这些标准已获得产业和服务供应商的广泛支持,并且引起了一场数字革命,使得更加普遍的交互式媒体得以迅速发展。目前,MPEG将研究重点转向了交互性更加高级的形式,在未来的几年里,技术的发展将使这种高级形式成为可能。这就是MPEG-4课题的目标,该课题预计在1998年底完成,该项目的完成可使用户达到关于音频视频内容交互性的多种形式,以及以一种整体的方式将人工的和自然的音频和视频信息溶合在一起。

     MPEG-4技术包含两个主要部分:视听对象的编码工具集和描述编码工具和编码对象的句法语言(syntatic language)。从技术的观点看,与传统编码标准最显著的不同是:接收者可以下载用于表示视听信息的语法描述,并且具有很快被VLSI(超大规模集成)技术所支持的特征。

     MPEG-4是一个正在制定的国际标准,它支持用于通信、访问和数字视听数据处理的新方法(特别是基于内容的)。考虑到低损耗、高性能技术提供的机会和面临迅速扩展的多媒体数据库的挑战,MPEG-4将提供灵活的框架和开放的工具集,这些工具将支持一些新型的和常规的功能。由于快速发展的技术使得工具软件的下载极为便利,因此这种方式极具吸引力。

     本文将介绍MPEG-4的特点以及由MPEG-4支持的功能、MPEG-4的结构和一些潜在的应用,还将介绍制定该标准的工作计划。

二、特点及其功能

     1.MPEG的特点

     远程通信、计算机和电视/电影工业之间的传统界限极为模糊。历史上原本属于某一领域的内容现已渗透到其他两个领域中。视频、声音和通信已进入计算机;交互性进入了电视;视频和交互性则进入了远程通信领域。看起来像一种聚集,实际上并非如此。这三种行业是从不同的技术角度来研究音像应用的。

     在当今世界,应对三种主要趋势予以关注:

     ●　向无线通信发展的趋势;

     ●　向交互式计算机应用发展的趋势;

     ●　视听数据的综合应用不断增长的趋势。

     对于传统意义上区分的各行业间的交叉,应综合考虑这三种趋势;目前的标准和正在制作的标准没有充分涉及这些新的需求。而MPEG-4的重点就是解决这些需求,即综合三种行业的通用应用,以提供便于交互的音频-视频编码、高压缩比和通用访问能力。为了采用迅速发展的相关技术的优点,MPEG-4标准将保证高度的灵活性和扩展性。

     基于内容的交互性包括人与音像画面中有意义的对象相互作用的能力。目前,这种交互作用局限于计算机图形,即人工合成的内容。对于新的交互式音像应用,能够提供与自然的、人工的及自然/人工混合的音像对象的相互作用极为重要。

     为了有效使用存储空间和传送带宽,需要有较高的压缩比。对于低比特率的应用,改善压缩效率非常重要。

     通用访问能力是指对有用的音像数据的访问可以在存储和传送媒体的很大范围内进行的鉴于移动通信的迅速崛起,通过无线网络进行这种应用的访问尤为重要。

     高度的灵活性和可扩展性由句法描述语言来保证,这种句法描述语言称为‘MPEG-4句法描述语言’(MSDL)。MSDL将在下面介绍。

     目前的视听标准是为从照像机和麦克风获取的自然内容的编码重现而设计的。由于上述三个领域的相互渗透,人工内容的应用在不断增长。因此,很显然的需求是一种既适合于自然对象又适合于人工对象的模式,它能够用来产生单一的音像序列。

     2.功能

     a.新的或改进的功能

     下述8个关键的功能是MPEG-4新的特点,可以认为现存的或其他正在制定的标准不能完全支持MPEG-4,这些功能由编码工具和MSDL的组合来支持。当特定应用需要时,灵活的MSDL允许使用不同的编码工具来提供这些功能的不同组合。

     这些功能如表1所述,在表1中根据它们是否涉及基于内容的交互性、压缩比或通用访问能力进行了分组。

     b.其他标准的功能

     除上述新的或改进的功能外,还有几种其他的重要功能,需要用它来支持已预见到的音频应用。与新的或改进的功能所不同的是,下面所列的功能已由现行的或其他正在制定的标准提供。

     ●　同步———对所表示的音频、视频和其他内容数据进行同步的能力;

     ●　辅助数据能力———为二进制数据比特流分配通道的能力;

     ●　虚拟通道分配的灵活性———动态地重新分配视频、音频或数据通道的能力;

     ●　低延迟模式(端对端或解码器)———对系统、音频和视频编码进行低延迟操作的能力;

     ●　用户控制———支持交互操作中用户控制的能力;

     ●　传送媒体交互运作———在各种媒体上进行运作的能力;

     ●　与其他音像系统的交互运作———与各种类型的终端相互作用的能力;

●   多点能力———具有多源或多目的地的能力;

●   安全———提供密码、鉴别和密钥管理的能力;

     ●　内容———对各种类型的可视画面和音频内容进行编码的能力(高的和中等质量的音频、宽带、窄带、智能和人工语言及人工音频);

     ●　格式———对各种格式的音频和视频进行编码的能力;

     ●　质量———对解码的音频或视频质量的评估。

三、MPEG-4的结构

     MPEG-4结构将为特定问题提供完整的解决方案,并且具有对最新的音像编码技术进行灵活复制的能力。从过去MPEG的经验看,预计MPEG-4由4个不同的部分组成:MPEG-4句法描述语言、工具、算法和轮廓。这些部分如下图所示:

     1.MPEG-4句法描述语言(MSDL)

     MPEG-4句法描述语言的目的是便于工具、算法和轮廓的选择、描述和下载,以及描述如何分析和处理基本的数据流。MSDL将提供解决下述有关方面的途径:

     ●　协商解码器的配置,该结果将决定轮廓;

     ●　描述轮廓:各组成部分以及这些组成部分间的链接;

     ●　在非特定机器语言中下载丢失部分,特别是在音像应用中;

     ●　用与所选择的轮廓相一致的语法和语义来传送数据(音像和其他)。

     2.工具

     工具是一种通过MPEG-4句法描述语言或使用MSDL描述的语言来访问的技术。它可通过软件或硬件来实现。

     工具示例:运行补偿和形状表示。

     3.算法

     算法是提供一个或多个功能工具的有机组合。

     算法示例:MPEG-1音频,MPEG-1视频和MPEG-2系统。

     4.轮廓

     轮廓是以特定的方式限定的一个算法或一组算法,用以解决一组特定的应用问题。     轮廓示例:MPEG-2 at Main Profile@ Main Level。

     5.哪些内容需要标准化

     以特定的方式可以将其下载到MPEG-4终端上的部分不需要标准化。按照MPEG的经验,下一步很可能就是对MPEG-4句法描述语言、一些工具和一些轮廓的标准化。虽然不必对所有的应用规定轮廓、算法甚至工具。但在轮廓级别范围内,下列应用是必须进行标准化的:

     ●　某些应用需要解码器开启与声音和图像重放之间的延迟尽可能的短;标准化的轮廓保证最快的开启。

     ●　某些应用使用了有限的易出错的传送资源,如无线网络。

     ●　下载花费时间较长,在临界阶段差错风险率较高。

     ●　尽管软件和硬件技术在发展,但那些费效最好的终端的生产仍然要求专门的编码硬件和特定软件平台。

     通过使用下载,MPEG-4标准将支持使用不在标准中出现的工具、算法和轮廓。

四、应用示例

     下面介绍得益于MPEG-4提供的新功能的三类应用示例,使人们对在今后的产品中如何使用这些功能有所了解。表2列出了基本的(即要实现的)和可选择的(即用于某些特定应用的)三种应用示例的功能。基本的/现的用‘E’表示可选择的用‘O’表示

     1.音像数据库访问

     这一类应用包括检索、处理、表示和音频、视频数据的存储。通过各种各样的无线和有线传输媒体,可以对一个通用数据库进行本地(如:从固态存储器)或远程访问。

     示例:

     ●音像终端,如专用数字辅助设备(PDA),用于支持电子新闻、电子黄页和移动信息的低容量网络(如:将来的蜂窝PSTN)。

     ●固态存储器上的视频存储,用于便携机上的播放/录制

     ●来自交互式视频目录的电视商场。

     2.音像通信和处理

     这一类应用包括有线或无线通信系统提供常规的人之间的服务。该类应用还包括传送和检索音像信息的方法。基本内容的功能能进行新型的交互,如:改进用户可选择区域的质量。

     示例:

     ●可视电话

     ●多点可视会议系统

     ●可视应答器

     ●可视e-mail

     3.远程监视和控制

     这一类应用包括在宽比特率的网络上使用照像机和麦克风。为了有效地传送和存储监视的音像数据需要高的压缩比。

     示例:

     ●建筑物、工地的安全监控等

     ●车辆交通监控

五、MPEG-4工作计划

     MPEG-4将研制并证实标准中的MSDL、工具、算法和轮廓。MPEG-4标准将提供其他相关信息,这些内容是全面地解决实际应用问题所需要的。工作计划分为设标阶段(1996.1结束)和联合研制阶段。

     在联合研制阶段,将吸收投标阶段的结果以制定出最佳标准,即研制灵活和可扩充的MPE G-4句法描述语言、音像编码工具、算法的轮廓的初始集合。

     目前,MPEG-4标准的研究已经产生了MSDL的工作组文件(WD),计划1997年7月形成WD的最后版本,1997年11月形成委员会草案(CD),1998年3月形成国际标准草案(DIS),1998年11月形成正式国际标准(IS)。我国已将MPEG-1标准转化为我国国家标准(等同采用),MPEG2也已列入今后两年的国家标准制定计划,我们将密切关注MPEG-4标准的研制动态,适时地将其转化为我国国家标准。


 弦截法
弦截法求方程的根是一种解方程得基本方法，在计算机编程中常用。他的思路是这样的：任取两个数，判断这两个数的函数值，如果函数值是同号，换两个数再试，直到两个数x1，x2对应的函数值为异号时为止，这时方程的解肯定在这两个数x1，x2之间。连接这两点所对应的函数值，连线与x轴的交点为新的x，若f(x)与f(x1)同号，则把x当作新的x1，将新的x1与x2连接，如此循环……如果f(x)与f(x1)异号，则把把x当作新的x2，将x1与新的x2连接，循环…… 

具体程序如下： 
#include <math.h> 
main() 
{ 
float x1,x2,f1,f2,x; 
do 
{ 
printf("input x1,x2:\n"); 
scanf("%f,%f",&x1,&x2); 
f1=f(x1);f2=f(x2); 
}while(f1*f2>=0); 
x=root(x1,x2); 
printf("A root of equation is %8.4f\n",x); 
} 

float root(float x1, float x2) 
{ 
int i; 
float x,y,y1; 
y1=f(x1); 
do 
{ 
x=xpoint(x1,x2); 
y=f(x); 
if(y*y1>0) 
{ 
y1=y; 
x1=x; 
}else 
x2=x; 
}while(fabs(y)>=0.0001); 
return (x); 
} 

float f(float x) 
{ 
float y; 
y=((x-5.0)*x+16)*x-80; 
return (y); 
} 
float xpoint(float x1,float x2) 
{ 
float y; 
y=(x1*f(x2)-x2*f(x1)) / (f(x2) - f(x1)); 
return (y) ; 
}
 
汉诺塔
 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

后来，这个传说就演变为汉诺塔游戏: 

1.有三根杆子A,B,C。A杆上有若干碟子  
2.每次移动一块碟子,小的只能叠在大的上面  
3.把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

此外，汉诺塔问题也是程序设计中的经典递归问题。

补充：汉诺塔的算法实现（c++）
#include <fstream>
#include <iostream>
using namespace std;

ofstream fout("out.txt");

void Move(int n,char x,char y)
{
        fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;
}

void Hannoi(int n,char a,char b,char c)
{
        if(n==1)
                Move(1,a,c);
        else
        {
                Hannoi(n-1,a,c,b);
                Move(n,a,c);
                Hannoi(n-1,b,a,c);
        }
}

int main()
{
        fout<<"以下是7层汉诺塔的解法:"<<endl;
        Hannoi(7,'a','b','c');
        fout.close();
        cout<<"输出完毕！"<<endl;
        return 0;
}

如果你的机子足够快，硬盘160G以上的化，可以把以上的程序改成64，运行完毕就是64汉诺塔的解法了。  


加密算法
加密算法 

一个加密系统S可以用数学符号描述如下： 

S={P, C, K, E, D} 

其中  

P——明文空间，表示全体可能出现的明文集合，

C——密文空间，表示全体可能出现的密文集合，

K——密钥空间，密钥是加密算法中的可变参数，

E——加密算法，由一些公式、法则或程序构成，

D——解密算法，它是E的逆。 

当给定密钥k&Icirc;K时，各符号之间有如下关系： 

C = Ek(P),                             对明文P加密后得到密文C

P = Dk(C) = Dk(Ek(P)),           对密文C解密后得明文P 

如用E-1 表示E的逆，D-1表示D的逆，则有： 

Ek = Dk-1且Dk = Ek-1 

因此，加密设计主要是确定E，D，K。 

RSA是Rivest、Shamir和Adleman提出来的基于数论非对称性(公开钥)加密算法。大整数的素因子难分解是RSA算法的基础。 

RSA在国外早已进入实用阶段，已研制出多种高速的RSA的专用芯片。尽管RSA的许多特性并不十分理想，但迫于信息安全的实际需要，许多重要的信息系统还是采用RSA作为基础加密机制。从RSA提出不久，我国有关部门就一直对它进行研究。从应用的角度看，软件实现的RSA已经开始用于计算机网络加密，用来完成密钥分配、数字签名等功能。 

除了RSA之外，还有DES(数据加密标准)。尽管DES公开了其加密算法并曾被美国列为“标准”，但很快被废弃。加密技术又回归到“算法保密”的传统上。

常见加密算法

DES（Data Encryption Standard）：数据加密标准，速度较快，适用于加密大量数据的场合； 

3DES（Triple DES）：是基于DES，对一块数据用三个不同的密钥进行三次加密，强度更高； 

RC2和 RC4：用变长密钥对大量数据进行加密，比 DES 快； 

IDEA（International Data Encryption Algorithm）国际数据加密算法，使用 128 位密钥提供非常强的安全性； 

RSA：由 RSA 公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件快的长度也是可变的； 

DSA（Digital Signature Algorithm）：数字签名算法，是一种标准的 DSS（数字签名标准）； 

AES（Advanced Encryption Standard）：高级加密标准，是下一代的加密算法标准，速度快，安全级别高，目前 AES 标准的一个实现是 Rijndael 算法； 

BLOWFISH，它使用变长的密钥，长度可达448位，运行速度很快； 

其它算法，如ElGamal、Deffie-Hellman、新型椭圆曲线算法ECC等。  


RSA加密算法
这是一个现在在网络上、银行系统、军事情报等等许多领域用处非常广泛的加密算法，已经深深的影响到我们每一个人。一个以RSA加密算法为业务的公司他的市值就可以达到5亿美元。他极大的保证了我们的交易的安全性，一组以RSA算法产生的密码是需要当前世界上所有电脑联机不断的工作25年才能够破解的，这个足以说明他的价值之大，用处之广泛。有一组资料说，以RSA加密算法进行的加密软件他的下载和使用量远远超过了WINDOWS软件、IE浏览器等等著名软件。这个是进入未来网络生活中不可缺少的工具。
1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。
    RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数（ 大于 100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。
  密钥对的产生:选择两个大素数，p 和q 。计算：   
n = p * q 
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用Euclid 算法计算解密密钥d, 满足
       e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) 
其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。 加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s <= n, s 尽可能的大。对应的密文是：
ci = mi^e ( mod n ) ( a ) 
解密时作如下计算：
mi = ci^d ( mod n ) ( b ) 
RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b ) 式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作 HASH 运算。
RSA 的安全性。 
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。
RSA的速度: 
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
RSA的选择密文攻击: 
RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： 
( XM )^d = X^d *M^d mod n 
前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way HashFunction 对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。
RSA的公共模数攻击。 
若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：
C1 = P^e1 mod n 
C2 = P^e2 mod n 
密码分析者知道n、e1、e2、C1和C2，就能得到P。因为e1和e2互质，故用Euclidean算法能找到r和s，满足：
r * e1 + s * e2 = 1 
假设r为负数，需再用Euclidean算法计算C1^(-1)，则 
( C1^(-1) )^(-r) * C2^s = P mod n
另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。
RSA的小指数攻击。 有一种提高RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。
RSA的缺点主要有： 
A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。
目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。 由柳洪平创建。  


RC4算法
RC4加密算法                                          
    RC4加密算法是大名鼎鼎的RSA三人组中的头号人物Ron Rivest在1987年设计的密钥长度可变的流加密算法簇。之所以称其为簇，是由于其核心部分的S-box长度可为任意，但一般为256字节。该算法的速度可以达到DES加密的10倍左右。
    RC4算法的原理很简单，包括初始化算法和伪随机子密码生成算法两大部分。假设S-box长度和密钥长度均为为n。先来看看算法的初始化部分（用类C伪代码表示）：
for (i=0; i<n; i++)
s=i;
j=0;
for (i=0; i<n; i++)
{
j=(j+s+k)%256;
swap(s, s[j]);
}
    在初始化的过程中，密钥的主要功能是将S-box搅乱，i确保S-box的每个元素都得到处理，j保证S-box的搅乱是随机的。而不同的S-box在经过伪随机子密码生成算法的处理后可以得到不同的子密钥序列，并且，该序列是随机的：
i=j=0;
while (明文未结束)
{
++i%=n;
j=(j+s)%n;
swap(s, s[j]);
sub_k=s((s+s[j])%n);
}
    得到的子密码sub_k用以和明文进行xor运算，得到密文，解密过程也完全相同。
    由于RC4算法加密是采用的xor，所以，一旦子密钥序列出现了重复，密文就有可能被破解。关于如何破解xor加密，请参看Bruce Schneier的Applied Cryptography一书的1.4节Simple XOR，在此我就不细说了。那么，RC4算法生成的子密钥序列是否会出现重复呢？经过我的测试，存在部分弱密钥，使得子密钥序列在不到100万字节内就发生了完全的重复，如果是部分重复，则可能在不到10万字节内就能发生重复，因此，推荐在使用RC4算法时，必须对加密密钥进行测试，判断其是否为弱密钥。
    但在2001年就有以色列科学家指出RC4加密算法存在着漏洞，这可能对无线通信网络的安全构成威胁。
以色列魏茨曼研究所和美国思科公司的研究者发现，在使用“有线等效保密规则”（WEP）的无线网络中，在特定情况下，人们可以逆转RC4算法的加密过程，获取密钥，从而将己加密的信息解密。实现这一过程并不复杂，只需要使用一台个人电脑对加密的数据进行分析，经过几个小时的时间就可以破译出信息的全部内容。
    专家说，这并不表示所有使用RC4算法的软件都容易泄密，但它意味着RC4算法并不像人们原先认为的那样安全。这一发现可能促使人们重新设计无线通信网络，并且使用新的加密算法。
 
MD5算法
    MD5的全称是Message-Digest Algorithm 5（信息-摘要算法），在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来，经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被"压缩"成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。不管是MD2、MD4还是MD5，它们都需要获得一个随机长度的信息并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似，但MD2的设计与MD4和MD5完全不同，那是因为MD2是为8位机器做过设计优化的，而MD4和MD5却是面向32位的电脑。这三个算法的描述和C语言源代码在Internet RFCs 1321中有详细的描述（http://www.ietf.org/rfc/rfc1321.txt），这是一份最权威的文档，由Ronald L. Rivest在1992年8月向IEFT提交。

　　Van Oorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数（Brute-Force Hash Function），而且他们猜测一个被设计专门用来搜索MD5冲突的机器（这台机器在1994年的制造成本大约是一百万美元）可以平均每24天就找到一个冲突。但单从1991年到2001年这10年间，竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一点，我们就可以看出这个瑕疵并没有太多的影响MD5的安全性。上面所有这些都不足以成为MD5的在实际应用中的问题。并且，由于MD5算法的使用不需要支付任何版权费用的，所以在一般的情况下（非绝密应用领域。但即便是应用在绝密领域内，MD5也不失为一种非常优秀的中间技术），MD5怎么都应该算得上是非常安全的了。

　　算法的应用

　　MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：

　　　MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461

　　这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改或者下载过程中线路不稳定引起的传输错误等），只要你对这个文件重新计算MD5时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的"抵赖"，这就是所谓的数字签名应用。

　　MD5还广泛用于加密和解密技术上。比如在UNIX系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。

　　正是因为这个原因，现在被黑客使用最多的一种破译密码的方法就是一种被称为"跑字典"的方法。有两种方法得到字典，一种是日常搜集的用做密码的字符串表，另一种是用排列组合方法生成的，先用MD5程序计算出这些字典项的MD5值，然后再用目标的MD5值在这个字典中检索。我们假设密码的最大长度为8位字节（8 Bytes），同时密码只能是字母和数字，共26+26+10=62个字符，排列组合出的字典的项数则是P(62,1)+P(62,2)….+P(62,8)，那也已经是一个很天文的数字了，存储这个字典就需要TB级的磁盘阵列，而且这种方法还有一个前提，就是能获得目标账户的密码MD5值的情况下才可以。这种加密技术被广泛的应用于UNIX系统中，这也是为什么UNIX系统比一般操作系统更为坚固一个重要原因。

　　算法描述

　　对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

　　在MD5算法中，首先需要对信息进行填充，使其字节长度对512求余的结果等于448。因此，信息的字节长度（Bits Length）将被扩展至N*512+448，即N*64+56个字节（Bytes），N为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，现在的信息字节长度=N*512+448+64=(N+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。

　　MD5中有四个32位被称作链接变量（Chaining Variable）的整数参数，他们分别为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。

　　当设置好这四个链接变量后，就开始进入算法的四轮循环运算。循环的次数是信息中512位信息分组的数目。

　　将上面四个链接变量复制到另外四个变量中：A到a，B到b，C到c，D到d。

　　主循环有四轮（MD4只有三轮），每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。
以一下是每次操作中用到的四个非线性函数（每轮一个）。

　　　F(X,Y,Z) =(X&Y)|((~X)&Z)
　　　G(X,Y,Z) =(X&Z)|(Y&(~Z))
　　　H(X,Y,Z) =X^Y^Z
　　　I(X,Y,Z)=Y^(X|(~Z))
　　　（&是与，|是或，~是非，^是异或）

　　这四个函数的说明：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。F是一个逐位运算的函数。即，如果X，那么Y，否则Z。函数H是逐位奇偶操作符。

　　假设Mj表示消息的第j个子分组（从0到15），<< 
　　　FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti)<< 　　　GG(a,b,c,d,Mj,s,ti)表示a=b+((a+(G(b,c,d)+Mj+ti)<< 　　　HH(a,b,c,d,Mj,s,ti)表示a=b+((a+(H(b,c,d)+Mj+ti)<< 　　　II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)<< 
　　这四轮（64步）是：

　　第一轮

　　　FF(a,b,c,d,M0,7,0xd76aa478)
　　　FF(d,a,b,c,M1,12,0xe8c7b756)
　　　FF(c,d,a,b,M2,17,0x242070db) 
          FF(b,c,d,a,M3,22,0xc1bdceee)
　　　FF(a,b,c,d,M4,7,0xf57c0faf)
　　　FF(d,a,b,c,M5,12,0x4787c62a)
　　　FF(c,d,a,b,M6,17,0xa8304613)
　　　FF(b,c,d,a,M7,22,0xfd469501)
　　　FF(a,b,c,d,M8,7,0x698098d8)
　　　FF(d,a,b,c,M9,12,0x8b44f7af)
　　　FF(c,d,a,b,M10,17,0xffff5bb1)
　　　FF(b,c,d,a,M11,22,0x895cd7be)
　　　FF(a,b,c,d,M12,7,0x6b901122)
　　　FF(d,a,b,c,M13,12,0xfd987193)
　　　FF(c,d,a,b,M14,17,0xa679438e)
　　　FF(b,c,d,a,M15,22,0x49b40821) 
　　第二轮

　　　GG(a,b,c,d,M1,5,0xf61e2562)
　　　GG(d,a,b,c,M6,9,0xc040b340)
　　　GG(c,d,a,b,M11,14,0x265e5a51)
　　　GG(b,c,d,a,M0,20,0xe9b6c7aa)
　　　GG(a,b,c,d,M5,5,0xd62f105d)
　　　GG(d,a,b,c,M10,9,0x02441453)
　　　GG(c,d,a,b,M15,14,0xd8a1e681)
　　　GG(b,c,d,a,M4,20,0xe7d3fbc8)
　　　GG(a,b,c,d,M9,5,0x21e1cde6)
　　　GG(d,a,b,c,M14,9,0xc33707d6)
　　　GG(c,d,a,b,M3,14,0xf4d50d87)
　　　GG(b,c,d,a,M8,20,0x455a14ed)
　　　GG(a,b,c,d,M13,5,0xa9e3e905)
　　　GG(d,a,b,c,M2,9,0xfcefa3f8)
　　　GG(c,d,a,b,M7,14,0x676f02d9)
　　　GG(b,c,d,a,M12,20,0x8d2a4c8a)

　　第三轮

　　　HH(a,b,c,d,M5,4,0xfffa3942)
　　　HH(d,a,b,c,M8,11,0x8771f681)
　　　HH(c,d,a,b,M11,16,0x6d9d6122)
　　　HH(b,c,d,a,M14,23,0xfde5380c)
　　　HH(a,b,c,d,M1,4,0xa4beea44)
　　　HH(d,a,b,c,M4,11,0x4bdecfa9)
　　　HH(c,d,a,b,M7,16,0xf6bb4b60)
　　　HH(b,c,d,a,M10,23,0xbebfbc70)
　　　HH(a,b,c,d,M13,4,0x289b7ec6)
　　　HH(d,a,b,c,M0,11,0xeaa127fa)
　　　HH(c,d,a,b,M3,16,0xd4ef3085)
　　　HH(b,c,d,a,M6,23,0x04881d05)
　　　HH(a,b,c,d,M9,4,0xd9d4d039)
　　　HH(d,a,b,c,M12,11,0xe6db99e5)
　　　HH(c,d,a,b,M15,16,0x1fa27cf8)
　　　HH(b,c,d,a,M2,23,0xc4ac5665)

　　第四轮

　　　II(a,b,c,d,M0,6,0xf4292244)
　　　II(d,a,b,c,M7,10,0x432aff97)
　　　II(c,d,a,b,M14,15,0xab9423a7)
　　　II(b,c,d,a,M5,21,0xfc93a039)
　　　II(a,b,c,d,M12,6,0x655b59c3)
　　　II(d,a,b,c,M3,10,0x8f0ccc92)
　　　II(c,d,a,b,M10,15,0xffeff47d)
　　　II(b,c,d,a,M1,21,0x85845dd1)
　　　II(a,b,c,d,M8,6,0x6fa87e4f)
　　　II(d,a,b,c,M15,10,0xfe2ce6e0)
　　　II(c,d,a,b,M6,15,0xa3014314)
　　　II(b,c,d,a,M13,21,0x4e0811a1)
　　　II(a,b,c,d,M4,6,0xf7537e82)
　　　II(d,a,b,c,M11,10,0xbd3af235)
　　　II(c,d,a,b,M2,15,0x2ad7d2bb)
　　　II(b,c,d,a,M9,21,0xeb86d391)

　　常数ti可以如下选择：

　　在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度。(4294967296等于2的32次方)
所有这些完成之后，将A、B、C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是A、B、C和D的级联。

　　当你按照我上面所说的方法实现MD5算法以后，你可以用以下几个信息对你做出来的程序作一个简单的测试，看看程序有没有错误。

　　　MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
　　　MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
　　　MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
　　　MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
　　　MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
　　　MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
d174ab98d277d9f5a5611c2c9f419d9f
　　　MD5 ("123456789012345678901234567890123456789012345678901234567890123456789
01234567890") = 57edf4a22be3c955ac49da2e2107b67a


　　MD5的安全性

　　MD5相对MD4所作的改进：

　　　1. 增加了第四轮；

　　　2. 每一步均有唯一的加法常数；

　　　3. 为减弱第二轮中函数G的对称性从(X&Y)|(X&Z)|(Y&Z)变为(X&Z)|(Y&(~Z))；

　　　4. 第一步加上了上一步的结果，这将引起更快的雪崩效应；

　　　5. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不相似；

　　　6. 近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应。各轮的位移量互不相同。  



数字签名
    简单地说,所谓数字签名就是附加在数据单元上的一些数据,或是对数据单元所作的密码变换。这种数据或变换允许数据单元的接收者用以确认数据单元的来源和数据单元的完整性并保护数据,防止被人(例如接收者)进行伪造。它是对电子形式的消息进行签名的一种方法,一个签名消息能在一个通信网络中传输。基于公钥密码体制和私钥密码体制都可以获得数字签名,目前主要是基于公钥密码体制的数字签名。包括普通数字签名和特殊数字签名。普通数字签名算法有RSA、ElGamal、Fiat-Shamir、Guillou- Quisquarter、Schnorr、Ong-Schnorr-Shamir数字签名算法、Des/DSA,椭圆曲线数字签名算法和有限自动机数字签名算法等。特殊数字签名有盲签名、代理签名、群签名、不可否认签名、公平盲签名、门限签名、具有消息恢复功能的签名等,它与具体应用环境密切相关。显然,数字签名的应用涉及到法律问题,美国联邦政府基于有限域上的离散对数问题制定了自己的数字签名标准(DSS)。

    数字签名（Digital Signature）技术是不对称加密算法的典型应用。数字签名的应用过程是，数据源发送方使用自己的私钥对数据校验和或其他与数据内容有关的变量进行加密处理，完成对数据的合法“签名”，数据接收方则利用对方的公钥来解读收到的“数字签名”，并将解读结果用于对数据完整性的检验，以确认签名的合法性。数字签名技术是在网络系统虚拟环境中确认身份的重要技术，完全可以代替现实过程中的“亲笔签字”，在技术和法律上有保证。在公钥与私钥管理方面，数字签名应用与加密邮件PGP技术正好相反。在数字签名应用中，发送者的公钥可以很方便地得到，但他的私钥则需要严格保密。

    数字签名包括普通数字签名和特殊数字签名。普通数字签名算法有RSA、ElGmal、Fiat-Shamir、Guillou-Quisquarter、Schnorr、Ong-Schnorr-Shamir数字签名算法、Des/DSA，椭圆曲线数字签名算法和有限自动机数字签名算法等。特殊数字签名有盲签名、代理签名、群签名、不可否认签名、公平盲签名、门限签名、具有消息恢复功能的签名等，它与具体应用环境密切相关。  


DC电平位移
  JPEG2000中进行预处理的一部分
  在对每一图像片进行正向离散小波变换之前，都要进行直流电平位移。目的是在解码时，能够从有符号的数值中正确恢复重构的无符号样本值。直流电平位移是对仅有无符号数组成的图像片的像素进行的。电平位移并不影响图像的质量。在解码端，在离散小波反变换之后，对重构的图像进行反向直流电平位移。  


蒙特卡罗方法
    蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。
    蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。
    蒙特·卡罗方法的基本原理：
    由概率定义知，某事件的概率可以用大量试验中该事件发生的频率来估算，当样本容量足够大时，可以认为该事件的发生频率即为其概率。因此，可以先对影响其可靠度的随机变量进行大量的随机抽样，然后把这些抽样值一组一组地代入功能函数式，确定结构是否失效，最后从中求得结构的失效概率。蒙特卡罗法正是基于此思路进行分析的。 

    设有统计独立的随机变量Xi(i=1，2，3，…，k)，其对应的概率密度函数分别为fx1，fx2，…，fxk，功能函数式为Z=g(x1，x2，…，xk)。 

    首先根据各随机变量的相应分布，产生N组随机数x1，x2，…，xk值，计算功能函数值Zi=g(x1，x2，…，xk)(i=1，2，…，N)，若其中有L组随机数对应的功能函数值Zi≤0，则当N→∞时，根据伯努利大数定理及正态随机变量的特性有：结构失效概率，可靠指标。 

    从蒙特卡罗方法的思路可看出，该方法回避了结构可靠度分析中的数学困难，不管状态函数是否非线性、随机变量是否非正态，只要模拟的次数足够多，就可得到一个比较精确的失效概率和可靠度指标。特别在岩土体分析中，变异系数往往较大，与JC法计算的可靠指标相比，结果更为精确，并且由于思路简单易于编制程序。
    在数学中的应用：
    通常蒙特·卡罗方法通过构造符合一定规则的随机数来解决数学上的各种问题。对于那些由于计算过于复杂而难以得到解析解或者根本没有解析解的问题，蒙特·卡罗方法是一种有效的求出数值解的方法。一般蒙特·卡罗方法在数学中最常见的应用就是蒙特·卡罗积分。  


LZW算法
  LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩. LZW压缩算法是Unisys的专利,有效期到2003年,所以对它的使用是有限制的   
字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩.
根据   Lempel-Ziv-Welch   Encoding   ，简称   LZW   的压缩算法，用任何一中语言来实现它.   
   LZW压缩算法的基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(String   Table)。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串(String)：由几个连续的字符组成；   前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：一个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.   
  LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.   
 
3DES
3DES是DES加密算法的一种模式，它使用3条64位的密钥对数据进行三次加密。数据加密标准（DES）是美国的一种由来已久的加密标准，它使用对称密钥加密法，并于1981年被ANSI组织规范为ANSI X.3.92。DES使用56位密钥和密码块的方法，而在密码块的方法中，文本被分成64位大小的文本块然后再进行加密。比起最初的DES，3DES更为安全。  


PGP
PGP—Pretty Good Privacy，是一个基于RSA公匙加密体系的邮件加密软件。可以用它对你的邮件保密以防止非授权者阅读，它还能对你的邮件加上数字签名从而使收信人可以确信邮件是你发来的。它让你可以安全地和你从未见过的人们通讯，事先并不需要任何保密的渠道用来传递密匙。它采用了：审慎的密匙管理，一种RSA和传统加密的杂合算法，用于数字签名的邮件文摘算法，加密前压缩等，还有一个良好的人机工程设计。它的功能强大，有很快的速度。而且它的源代码是免费的。  


进制
数制是人们利用符号进行计数的科学方法。数制有很多种，在计算机中常用的数制有：十进制，二进制和十六进制。 

1． 十进制数 

人们通常使用的是十进制。它的特点有两个：有0，1，2….9十个基本字符组成,十进制数运算是按“逢十进一”的规则进行的. 

在计算机中,除了十进制数外,经常使用的数制还有二进制数和十六进制数.在运算中它们分别遵循的是逢二进一和逢十六进一的法则. 

2． 二进制数 

3． 二进制数有两个特点：它由两个基本字符0，1组成，二进制数运算规律是逢二进一。 

为区别于其它进制数，二进制数的书写通常在数的右下方注上基数2，或加后面加B表示。 

例如：二进制数10110011可以写成（10110011）2,或写成10110011B,对于十进制数可以不加注.计算机中的数据均采用二进制数表示,这是因为二进制数具有以下特点： 

1） 二进制数中只有两个字符0和1，表示具有两个不同稳定状态的元器件。例如，电路中有，无电流，有电流用1表示，无电流用0表示。类似的还比如电路中电压的高，低，晶体管的导通和截止等。 

2） 二进制数运算简单，大大简化了计算中运算部件的结构。 

二进制数的加法和乘法运算如下： 

0+0=0 0+1=1+0=1 1+1=10 

0×0=0 0×1=1×0=0 1×1=1 

由于二进制数在使用中位数太长,不容易记忆,所以又提出了十六进制数. 

3.十六进制数 

十六进制数有两个基本特点:它由十六个字符0～9以及A，B，C，D，E，F组成（它们分别表示十进制数0～15），十六进制数运算规律是逢十六进一，鹩谄渌剖剖氖樾赐ǔT谑挠蚁路阶⑸匣保叮蚣雍竺婕樱缺硎尽?/SPAN> 

例如：十六进制数4AC8可写成（4AC8）16，或写成4AC8H。 

4． 数的位权概念 

5． 一个十进制数110，其中百位上的1表示1个102，既100，十位的1表示1个101，即10，个位的0表示0个100，即0。 

一个二进制数110，其中高位的1表示1个22，即4，低位的1表示1个21，即2，最低位的0表示0个20，即0。 

一个十六进制数110，其中高位的1表示1个162，即256，低位的1表示1个161，即16，最低位的0表示0个160，即0。 

可见，在数制中，各位数字所表示值的大小不仅与该数字本身的大小有关，还与该数字所在的位置有关，我们称这关系为数的位权。 

十进制数的位权是以10为底的幂，二进制数的位权是以2为底的幂，十六进制数的位权是以16为底的幂。数位由高向低，以降幂的方式排列。 

二、进数制之间的转换 

1.二进制数、十六进制数转换为十进制数（按权求和） 

二进制数、十六进制数转换为十进制数的规律是相同的。把二进制数（或十六进制数）按位权形式展开多项式和的形式，求其最后的和，就是其对应的十进制数——简称“按权求和”. 

例如:把(1001.01)2转换为十进制数。 

解：（1001.01）2 

=1×23+0×22+0×21+1×20+0×2-1+1×2-2 

=8+0+0+1+0.5+0.25 

=9.75 

把(38A.11)16转换为十进制数 

解:(38A.11)16 

=3×162+8×16+10×160+1×16-1+1×16-2 

=768+128+10+0.0625+0.0039 

=906.0664 

2.十进制数转换为二进制数,十六进制数(除2/16取余法) 

整数转换.一个十进制整数转换为二进制整数通常采用除二取余法,即用2连续除十进制数,直到商为0,逆序排列余数即可得到――简称除二取余法． 

例：将25转换为二进制数 

解:25÷2=12 余数1 

12÷2=6 余数0 

6÷2=3 余数0 

3÷2=1 余数1 

1÷2=0 余数1 

所以25=(11001)2 

同理,把十进制数转换为十六进制数时,将基数2转换成16就可以了. 

例:将25转换为十六进制数 

解:25÷16=1 余数9 

1÷16=0 余数1 

所以25=(19)16 

3.二进制数与十六进制数之间的转换 

由于4位二进制数恰好有16个组合状态,即1位十六进制数与4位二进制数是一一对应的.所以,十六进制数与二进制数的转换是十分简单的. 

(1)十六进制数转换成二进制数,只要将每一位十六进制数用对应的4位二进制数替代即可――简称位分四位. 

例:将(4AF8B)16转换为二进制数. 

解: 4 A F 8 B 

0100 1010 1111 1000 1011 

所以(4AF8B)16=(1001010111110001011)2 

(2)二进制数转换为十六进制数,分别向左,向右每四位一组,依次写出每组4位二进制数所对应的十六进制数――简称四位合一位. 

例:将二进制数(111010110)2转换为十六进制数. 

解: 0001 1101 0110 

1 D 6 

所以(111010110)2=1D6H 

转换时注意最后一组不足4位时必须加0补齐4位  


快速傅里叶变换
快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。

设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。  


对称加密算法
对称加密算法 对称加密算法是应用较早的加密算法，技术成熟。在对称加密算法中，数据发信方将明文（原始数据）和加密密钥一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先必须知道加密密钥。对称加密算法的特点是算法公开、计算量小、加密速度快、加密效率高。不足之处是，交易双方都使用同样钥匙，安全性得不到保证。此外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的惟一钥匙，这会使得发收信双方所拥有的钥匙数量成几何级数增长，密钥管理成为用户的负担。对称加密算法在分布式网络系统上使用较为困难，主要是因为密钥管理困难，使用成本较高。在计算机专网系统中广泛使用的对称加密算法有DES和IDEA等。美国国家标准局倡导的AES即将作为新标准取代DES。  


不对称加密算法
不对称加密算法使用两把完全不同但又是完全匹配的一对钥匙—公钥和私钥。在使用不对称加密算法加密文件时，只有使用匹配的一对公钥和私钥，才能完成对明文的加密和解密过程。加密明文时采用公钥加密，解密密文时使用私钥才能完成，而且发信方（加密者）知道收信方的公钥，只有收信方（解密者）才是唯一知道自己私钥的人。不对称加密算法的基本原理是，如果发信方想发送只有收信方才能解读的加密信息，发信方必须首先知道收信方的公钥，然后利用收信方的公钥来加密原文；收信方收到加密密文后，使用自己的私钥才能解密密文。显然，采用不对称加密算法，收发信双方在通信之前，收信方必须将自己早已随机生成的公钥送给发信方，而自己保留私钥。由于不对称算法拥有两个密钥，因而特别适用于分布式系统中的数据加密。广泛应用的不对称加密算法有RSA算法和美国国家标准局提出的DSA。以不对称加密算法为基础的加密技术应用非常广泛。  


不可逆加密算法
不可逆加密算法的特征是加密过程中不需要使用密钥，输入明文后由系统直接经过加密算法处理成密文，这种加密后的数据是无法被解密的，只有重新输入明文，并再次经过同样不可逆的加密算法处理，得到相同的加密密文并被系统重新识别后，才能真正解密。显然，在这类加密过程中，加密是自己，解密还得是自己，而所谓解密，实际上就是重新加一次密，所应用的“密码”也就是输入的明文。不可逆加密算法不存在密钥保管和分发问题，非常适合在分布式网络系统上使用，但因加密计算复杂，工作量相当繁重，通常只在数据量有限的情形下使用，如广泛应用在计算机系统中的口令加密，利用的就是不可逆加密算法。近年来，随着计算机系统性能的不断提高，不可逆加密的应用领域正在逐渐增大。在计算机网络中应用较多不可逆加密算法的有RSA公司发明的MD5算法和由美国国家标准局建议的不可逆加密标准SHS(Secure Hash Standard:安全杂乱信息标准)等。  
